Calculer la distance entre deux sommets
Énoncé
Soit M = (0 , 1 , 0 , 0 ; 0 , 0 , 1 , 0 ; 0 , 0 , 0 , 1 ; 1 , 0 , 0 , 0) la matrice d'adjacence d'un graphe avec 4 sommets.
Calculer la distance d(s₁, s₄) entre les sommets s₁ et s₄.
Indice : La distance est la longueur du plus court chemin. Calcule M, M², M³ jusqu'à trouver (Mᵏ)₁,₄ > 0.
Correction
- Étape 1 : La distance d(s₁, s₄) est la longueur du plus court chemin. On teste donc les longueurs dans l'ordre croissant et l'on s'arrête à la première qui marche.
La question est bien posée : le graphe a 4 sommets, donc si un chemin existe il en existe un de longueur ≤ 3. Trois essais au plus.
- Étape 2 : Longueur 1 ? On regarde M directement : m₁,₄ = 0, donc il n'y a pas d'arc de s₁ à s₄.
- Étape 3 : Longueur 2 ? Chaque ligne de M n'ayant qu'un seul 1, la ligne i de M² est simplement la ligne vers laquelle i pointe :
M² = (0, 0, 1, 0 ; 0, 0, 0, 1 ; 1, 0, 0, 0 ; 0, 1, 0, 0)
- Étape 4 : (M²)₁,₄ = 0 : toujours rien. En deux arcs depuis s₁, on atteint s₃ et pas s₄.
- Étape 5 : Longueur 3 ? On applique le même décalage une fois de plus :
M³ = (0, 0, 0, 1 ; 1, 0, 0, 0 ; 0, 1, 0, 0 ; 0, 0, 1, 0)
- Étape 6 : (M³)₁,₄ = 1 > 0 : il existe un chemin, et un seul. La distance vaut donc 3 :
d(s₁, s₄) = 3 s₁ → s₂ → s₃ → s₄
- Étape 7 : Le graphe est un cycle de longueur 4, ce que confirme le décalage régulier des matrices. Pour aller de s₁ à s₄, il faut donc faire presque le tour — d'où une distance de 3 alors que les sommets sont voisins sur le dessin.
L'ordre des essais n'est pas facultatif :
Sauter directement à M³ donnerait 1 > 0 et l'on conclurait d = 3 — juste ici, par chance.
Mais si (M²)₁,₄ avait été non nul, la vraie distance aurait été 2 et la réponse fausse. La distance est le plus PETIT k qui marche, donc l'ordre croissant est obligatoire.
Sur un cycle orienté, la distance se lit sans matrices :
d(sᵢ, sⱼ) = nombre de crans à avancer dans le sens du cycle. De s₁ à s₄ : trois crans.
Les matrices confirment ce que le dessin donne immédiatement — ce qui en fait un bon contrôle.