Analyser un graphe avec matrice de connexité

Énoncé

Soit M = (0 , 1 , 0 ; 1 , 0 , 1 ; 0 , 1 , 0) la matrice d'adjacence d'un graphe. Calculer la matrice de connexité C et déterminer si le graphe est fortement connexe. En déduire le diamètre du graphe.

Indice : Calcule C = M + M² + M³. Le graphe est fortement connexe si tous les coefficients non diagonaux sont strictement positifs. Le diamètre est la distance maximale entre deux sommets.

Correction

  1. Étape 1 : Un détail à relever avant tout calcul : M est symétrique. Le graphe est donc NON orienté — c'est le chemin s₁ - s₂ - s₃, où chaque arête se parcourt dans les deux sens. Conséquence immédiate : la connexité et la forte connexité coïncident, puisque tout aller possède son retour.
  2. Étape 2 : Les puissances. La ligne 2 de M contient deux 1, donc la ligne 2 de M² est la SOMME des lignes 1 et 3 :

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

  3. Étape 3 : Les coefficients ne sont plus des 0 et des 1, et c'est instructif : (M²)₂,₂ = 2 signifie qu'il existe deux chemins de longueur 2 de s₂ vers lui-même — l'aller-retour vers s₁ et l'aller-retour vers s₃.
  4. Étape 4 : La matrice de connexité :

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

  5. Étape 5 : Tous les coefficients sont strictement positifs, donc le graphe est fortement connexe : chaque sommet atteint tous les autres.
  6. Étape 6 : Le diamètre est la plus grande des distances entre deux sommets. On les relève toutes : d(s₁, s₂) = 1 et d(s₂, s₃) = 1, car m₁,₂ = m₂,₃ = 1.
  7. Étape 7 : Pour le dernier couple : m₁,₃ = 0 mais (M²)₁,₃ = 1, donc la distance vaut 2 — il faut passer par s₂. C'est la plus grande, d'où :

    diam(G) = 2

  8. Étape 8 : Le diamètre mesure la « largeur » du graphe : deux sauts suffisent pour aller n'importe où. Sur un chemin à trois sommets, c'est le maximum possible. Le diamètre est un maximum de MINIMUMS : On prend d'abord le plus COURT chemin entre chaque paire, puis le plus GRAND de ces nombres. Inverser les deux quantificateurs n'a aucun sens : le plus long chemin entre deux sommets est infini dès qu'il existe un circuit, puisqu'on peut tourner indéfiniment. La symétrie divise le travail par deux : Sur un graphe non orienté, d(sᵢ, sⱼ) = d(sⱼ, sᵢ) : il n'y a que trois distances à calculer ici au lieu de six. Et cela se vérifie sur C, qui est symétrique elle aussi — une matrice de connexité non symétrique sur un graphe non orienté signalerait une erreur de calcul.