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ᵢ_₀, sᵢ_₁, …, sᵢ_ₖ telle que :

(sᵢ_ⱼ, sᵢ_ⱼ₊₁) ∈ A pour tout j = 0, …, k-1

On dit que le chemin va de sᵢ_₀ (sommet initial) à sᵢ_ₖ (sommet terminal).

Circuit : Un circuit (ou cycle orienté) est un chemin dont le sommet initial et le sommet terminal sont identiques : sᵢ_₀ = sᵢ_ₖ.

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ᵏ)ᵢ,ⱼ donne le nombre de chemins de longueur exactement k allant du sommet sᵢ au sommet sⱼ.

Exemple : Soit M = (0 , 1 , 1 ; 0 , 0 , 1 ; 1 , 0 , 0) la matrice d'adjacence d'un graphe.

Calculons M² :

M² = (1 , 0 , 1 ; 1 , 0 , 0 ; 0 , 1 , 1)

  • (M²)₁,₃ = 1 : il existe 1 chemin de longueur 2 de s₁ à s₃
  • (M²)₂,₁ = 1 : il existe 1 chemin de longueur 2 de s₂ à s₁
  • (M²)₁,₁ = 1 : il existe 1 circuit de longueur 2 passant par s₁

Méthode pour compter les chemins : Pour trouver le nombre de chemins de longueur k de sᵢ à sⱼ :

  1. Construire la matrice d'adjacence M
  2. Calculer Mᵏ
  3. Lire le coefficient (Mᵏ)ᵢ,ⱼ

3. Matrice de connexité

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

C = M + M² + M³ + ⋯ + Mⁿ

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

Le coefficient cᵢ,ⱼ donne le nombre total de chemins de longueur entre 1 et n allant de sᵢ à sⱼ. (Pour deux sommets distincts, un chemin de longueur au plus n - 1 suffit toujours ; la puissance n sert aux circuits qui reviennent à leur point de départ.)

Propriété : Si cᵢ,ⱼ > 0, alors il existe au moins un chemin de sᵢ à sⱼ.

Si cᵢ,ⱼ = 0, alors il n'existe aucun chemin de sᵢ à sⱼ.

Exemple : Pour un graphe avec M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) :

  • M² = (0 , 0 , 1 ; 1 , 0 , 0 ; 0 , 1 , 0)
  • M³ = (1 , 0 , 0 ; 0 , 1 , 0 ; 0 , 0 , 1) = I₃

La matrice de connexité est :

C = M + M² + M³ = (1 , 1 , 1 ; 1 , 1 , 1 ; 1 , 1 , 1)

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ᵢ, sⱼ), il existe un chemin de sᵢ à sⱼ et un chemin de sⱼ à sᵢ.

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ᵢ,ⱼ > 0.

Exemple : Le graphe avec matrice d'adjacence M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) est fortement connexe car :

  • De s₁ à s₂ : chemin s₁ → s₂
  • De s₂ à s₁ : chemin s₂ → s₃ → s₁
  • 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ᵢ,ⱼ > 0 et cⱼ,ᵢ > 0
  3. Grouper les sommets selon cette relation d'équivalence

6. Distance dans un graphe

Distance : La distance d(sᵢ, sⱼ) entre deux sommets sᵢ et sⱼ dans un graphe orienté est :

  • La longueur du plus court chemin de sᵢ à sⱼ s'il existe
  • +∞ s'il n'existe aucun chemin de sᵢ à sⱼ

Calcul de la distance : Pour trouver la distance entre sᵢ et sⱼ :

  1. Calculer M, M², M³, …
  2. La distance est le plus petit k tel que (Mᵏ)ᵢ,ⱼ > 0
  3. Si aucun k ne vérifie cette condition (pour k ≤ n-1), alors d(sᵢ, sⱼ) = +∞

Exemple : Dans le graphe avec M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) :

  • d(s₁, s₂) = 1 car (M)₁,₂ = 1
  • d(s₁, s₃) = 2 car (M)₁,₃ = 0 mais (M²)₁,₃ = 1
  • d(s₂, s₁) = 2 car (M)₂,₁ = 0 mais (M²)₂,₁ = 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 :

diam(G) = maxᵢ,ⱼ d(sᵢ, sⱼ)

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ᵢ, sⱼ) chaque fois qu'il existe un chemin (de longueur quelconque) de sᵢ à sⱼ 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 :

M^* = 1 si cᵢ,ⱼ > 0 | 0 sinon


9. Application : détection de cycles

Détection de circuits : Un graphe orienté contient un circuit si et seulement si la diagonale de Mᵏ 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ᵢ si et seulement si (Mᵏ)ᵢ,ᵢ > 0.

Exemple : Pour M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) :

  • (M³)₁,₁ = 1 : il existe un circuit de longueur 3 passant par s₁
  • (M³)₂,₂ = 1 : il existe un circuit de longueur 3 passant par s₂
  • (M³)₃,₃ = 1 : il existe un circuit de longueur 3 passant par s₃

C'est le même circuit s₁ → s₂ → s₃ → s₁.


À retenir

Résumé :

  1. Chemin de longueur k : (Mᵏ)ᵢ,ⱼ donne le nombre de chemins de sᵢ à sⱼ

  2. Matrice de connexité : C = M + M² + ⋯ + Mⁿ⁻¹ 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ᵏ jusqu'à trouver (Mᵏ)ᵢ,ⱼ > 0

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

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

  1. Construire M
  2. Calculer M², M³, … jusqu'à Mⁿ⁻¹
  3. Former C = M + M² + ⋯ + Mⁿ⁻¹
  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.