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
- É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.
- É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)
- É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₃.
- Étape 4 : La matrice de connexité :
C = M + M² + M³ = (1, 3, 1 ; 3, 2, 3 ; 1, 3, 1)
- Étape 5 : Tous les coefficients sont strictement positifs, donc le graphe est fortement connexe : chaque sommet atteint tous les autres.
- É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.
- É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
- É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.