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

  1. É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.
  2. Étape 2 : Longueur 1 ? On regarde M directement : m₁,₄ = 0, donc il n'y a pas d'arc de s₁ à s₄.
  3. É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)

  4. Étape 4 : (M²)₁,₄ = 0 : toujours rien. En deux arcs depuis s₁, on atteint s₃ et pas s₄.
  5. É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)

  6. É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₄

  7. É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.