Calculer la distance entre deux sommets

Énoncé

Soit M = pmatrix 0 & 1 & 0 & 0 0 & 0 & 1 & 0 0 & 0 & 0 & 1 1 & 0 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe avec 4 sommets. Calculer la distance d(s_1, s_4) entre les sommets s_1 et s_4.

Indice : La distance est la longueur du plus court chemin. Calcule M, M^2, M^3 jusqu'à trouver (M^k)_{1,4} > 0.

Correction

  1. Étape 1 : La distance d(s_1, s_4) 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_{1,4} = 0, donc il n'y a pas d'arc de s_1 à s_4.
  3. Étape 3 : Longueur 2 ? Chaque ligne de M n'ayant qu'un seul 1, la ligne i de M^2 est simplement la ligne vers laquelle i pointe :

    M^2 = pmatrix 0&0&1&0 0&0&0&1 1&0&0&0 0&1&0&0 pmatrix

  4. Étape 4 : (M^2)_{1,4} = 0 : toujours rien. En deux arcs depuis s_1, on atteint s_3 et pas s_4.
  5. Étape 5 : Longueur 3 ? On applique le même décalage une fois de plus :

    M^3 = pmatrix 0&0&0&1 1&0&0&0 0&1&0&0 0&0&1&0 pmatrix

  6. Étape 6 : (M^3)_{1,4} = 1 > 0 : il existe un chemin, et un seul. La distance vaut donc 3 :

    d(s_1, s_4) = 3 s_1 s_2 s_3 s_4

  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_1 à s_4, 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^3 donnerait 1 > 0 et l'on conclurait d = 3 — juste ici, par chance. Mais si (M^2)_{1,4} 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_i, s_j) = nombre de crans à avancer dans le sens du cycle. De s_1 à s_4 : trois crans. Les matrices confirment ce que le dessin donne immédiatement — ce qui en fait un bon contrôle.