Calculer le nombre de chemins de longueur 2

Énoncé

Soit M = (0 , 1 , 0 ; 0 , 0 , 1 ; 1 , 0 , 0) la matrice d'adjacence d'un graphe. Calculer M² et interpréter le coefficient (M²)₁,₃.

Indice : Calcule M² en multipliant M par elle-même. Le coefficient (M²)ᵢ,ⱼ donne le nombre de chemins de longueur 2 de sᵢ à sⱼ.

Correction

  1. Étape 1 : Le fait central du chapitre, et celui qui donne tout son intérêt aux matrices d'adjacence : Le théorème des chemins : (Mᵏ)ᵢ,ⱼ = nombre de chemins de longueur exactement k allant de i à j. Pourquoi ? Parce que (M²)ᵢ,ⱼ = Σᵣ mᵢ,ᵣ mᵣ,ⱼ : chaque terme vaut 1 précisément quand il existe un arc i → r ET un arc r → j, c'est-à-dire un chemin i → r → j. La somme les compte tous.
  2. Étape 2 : Le produit, sans effort. Chaque ligne de M ne contient qu'un seul 1 : la ligne 1 pointe vers 2, la ligne 2 vers 3, la ligne 3 vers 1. Or la ligne i de M² est la somme des lignes de M désignées par les 1 de la ligne i. Donc : ligne 1 de M² = ligne 2 de M · ligne 2 de M² = ligne 3 de M · ligne 3 de M² = ligne 1 de M
  3. Étape 3 : On recopie ces trois lignes dans le bon ordre :

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

  4. Étape 4 : Interprétation. (M²)₁,₃ = 1 : il existe exactement un chemin de longueur 2 de s₁ à s₃.
  5. Étape 5 : On peut l'exhiber, ce qui vérifie tout d'un coup :

    s₁ → s₂ → s₃ car m₁,₂ = 1 et m₂,₃ = 1

  6. Étape 6 : Longueur = nombre d'ARCS, pas de sommets : le chemin ci-dessus traverse trois sommets et compte deux arcs, donc sa longueur est 2. M² ne compte QUE la longueur exacte : (M²)₁,₃ = 1 ne dit pas « il y a un chemin de s₁ à s₃ » mais « il y en a un de longueur 2 ». Pour savoir s'il en existe un de longueur quelconque, il faut sommer M + M² + … — c'est la matrice de connexité, employée aux exercices 39008 et 39015. La lecture par lignes vaut pour toute puissance : Ligne i de Mᵏ⁺¹ = somme des lignes de Mᵏ pointées par les 1 de la ligne i de M. Sur les matrices creuses de ce chapitre, elle remplace complètement le produit posé.