Chemins et connexité dans un graphe

Graphes et matrices — Terminale Maths Expertes

Chemins et connexité dans un graphe

Introduction

La notion de connexité permet de caractériser la structure d'un graphe et de déterminer s'il est possible de se déplacer entre différents sommets. Les matrices d'adjacence fournissent des outils puissants pour analyser ces propriétés.

1. Chemins et circuits

Chemin : Un chemin (ou chaîne orientée) de longueur k dans un graphe orienté G = (S, A) est une séquence de k+1 sommets s_{i_0}, s_{i_1}, , s_{i_k} telle que :

[formule]

On dit que le chemin va de s_{i_0} (sommet initial) à s_{i_k} (sommet terminal).

Circuit : Un circuit (ou cycle orienté) est un chemin dont le sommet initial et le sommet terminal sont identiques : s_{i_0} = s_{i_k}.

Un circuit de longueur k est un chemin fermé de longueur k.

Exemple : Dans le graphe avec arcs : (A, B), (B, C), (C, A), (A, D) :

  • A B C est un chemin de longueur 2
  • A B C A est un circuit de longueur 3
  • A D est un chemin de longueur 1

2. Chemins et puissances de la matrice d'adjacence

Théorème fondamental : Soit M la matrice d'adjacence d'un graphe orienté G.

Pour tout entier k 1, le coefficient (M^k)_{i,j} donne le nombre de chemins de longueur exactement k allant du sommet s_i au sommet s_j.

Exemple : Soit M = pmatrix 0 & 1 & 1 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe.

Calculons M^2 :

[formule]

  • (M^2)_{1,3} = 1 : il existe 1 chemin de longueur 2 de s_1 à s_3
  • (M^2)_{2,1} = 1 : il existe 1 chemin de longueur 2 de s_2 à s_1
  • (M^2)_{1,1} = 1 : il existe 1 circuit de longueur 2 passant par s_1

Méthode pour compter les chemins : Pour trouver le nombre de chemins de longueur k de s_i à s_j :

  1. Construire la matrice d'adjacence M
  2. Calculer M^k
  3. Lire le coefficient (M^k)_{i,j}

3. Matrice de connexité

Matrice de connexité : La matrice de connexité C d'un graphe orienté est définie par :

[formule]

où n est le nombre de sommets et M la matrice d'adjacence.

Le coefficient c_{i,j} donne le nombre total de chemins de longueur entre 1 et n-1 allant de s_i à s_j.

Propriété : Si c_{i,j} > 0, alors il existe au moins un chemin de s_i à s_j.

Si c_{i,j} = 0, alors il n'existe aucun chemin de s_i à s_j.

Exemple : Pour un graphe avec M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix :

  • M^2 = pmatrix 0 & 0 & 1 1 & 0 & 0 0 & 1 & 0 pmatrix
  • M^3 = pmatrix 1 & 0 & 0 0 & 1 & 0 0 & 0 & 1 pmatrix = I_3

La matrice de connexité est :

[formule]

Tous les coefficients sont positifs, donc il existe des chemins entre tous les couples de sommets.

4. Connexité forte

Graphe fortement connexe : Un graphe orienté G est fortement connexe (ou fortement connecté) si pour tout couple de sommets (s_i, s_j), il existe un chemin de s_i à s_j et un chemin de s_j à s_i.

Caractérisation matricielle : Un graphe orienté est fortement connexe si et seulement si sa matrice de connexité C a tous ses coefficients strictement positifs (sauf éventuellement la diagonale).

Autrement dit, pour tout i j, on a c_{i,j} > 0.

Exemple : Le graphe avec matrice d'adjacence M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix est fortement connexe car :

  • De s_1 à s_2 : chemin s_1 s_2
  • De s_2 à s_1 : chemin s_2 s_3 s_1
  • Tous les autres couples sont accessibles mutuellement

5. Composantes fortement connexes

Composante fortement connexe : Une composante fortement connexe d'un graphe orienté est un sous-graphe maximal fortement connexe.

Deux sommets appartiennent à la même composante fortement connexe s'il existe un chemin dans les deux sens entre eux.

Algorithme de recherche des composantes : Pour trouver les composantes fortement connexes :

  1. Construire la matrice de connexité C
  2. Identifier les couples (i,j) tels que c_{i,j} > 0 et c_{j,i} > 0
  3. Grouper les sommets selon cette relation d'équivalence

6. Distance dans un graphe

Distance : La distance d(s_i, s_j) entre deux sommets s_i et s_j dans un graphe orienté est :

  • La longueur du plus court chemin de s_i à s_j s'il existe
    • s'il n'existe aucun chemin de s_i à s_j

Calcul de la distance : Pour trouver la distance entre s_i et s_j :

  1. Calculer M, M^2, M^3,
  2. La distance est le plus petit k tel que (M^k)_{i,j} > 0
  3. Si aucun k ne vérifie cette condition (pour k n-1), alors d(s_i, s_j) = +

Exemple : Dans le graphe avec M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix :

  • d(s_1, s_2) = 1 car (M)_{1,2} = 1
  • d(s_1, s_3) = 2 car (M){1,3} = 0 mais (M^2){1,3} = 1
  • d(s_2, s_1) = 2 car (M){2,1} = 0 mais (M^2){2,1} = 1

7. Diamètre d'un graphe

Diamètre : Le diamètre d'un graphe orienté fortement connexe est le maximum des distances entre tous les couples de sommets :

[formule]

Borne supérieure : Pour un graphe avec n sommets, le diamètre est au plus n-1 (si le graphe est fortement connexe).

8. Matrice de fermeture transitive

Fermeture transitive : La fermeture transitive d'un graphe orienté G est le graphe G^* obtenu en ajoutant un arc (s_i, s_j) chaque fois qu'il existe un chemin (de longueur quelconque) de s_i à s_j dans G.

Matrice de fermeture transitive : La matrice d'adjacence de la fermeture transitive est la matrice booléenne obtenue à partir de la matrice de connexité C :

[formule]

9. Application : détection de cycles

Détection de circuits : Un graphe orienté contient un circuit si et seulement si la diagonale de M^k contient au moins un coefficient non nul pour un certain k 1.

Plus précisément, il existe un circuit de longueur k passant par s_i si et seulement si (M^k)_{i,i} > 0.

Exemple : Pour M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix :

  • (M^3)_{1,1} = 1 : il existe un circuit de longueur 3 passant par s_1
  • (M^3)_{2,2} = 1 : il existe un circuit de longueur 3 passant par s_2
  • (M^3)_{3,3} = 1 : il existe un circuit de longueur 3 passant par s_3

C'est le même circuit s_1 s_2 s_3 s_1.

À retenir

Résumé :

  1. Chemin de longueur k : (M^k)_{i,j} donne le nombre de chemins de s_i à s_j

  2. Matrice de connexité : C = M + M^2 + + M^{n-1} indique l'existence de chemins

  3. Graphe fortement connexe : tous les coefficients non diagonaux de C sont strictement positifs

  4. Distance : longueur du plus court chemin, trouvée en calculant M^k jusqu'à trouver (M^k)_{i,j} > 0

  5. Circuits : détectés par les coefficients diagonaux non nuls de M^k

Méthode pratique : Pour analyser la connexité d'un graphe :

  1. Construire M
  2. Calculer M^2, M^3, jusqu'à M^{n-1}
  3. Former C = M + M^2 + + M^{n-1}
  4. Analyser les coefficients de C pour déterminer la connexité

L'analyse des chemins et de la connexité par les matrices permet de comprendre la structure globale d'un graphe et de résoudre de nombreux problèmes pratiques.