Calculer le nombre de chemins de longueur 2

Énoncé

Soit M = pmatrix 0 & 1 & 0 0 & 0 & 1 1 & 0 & 0 pmatrix la matrice d'adjacence d'un graphe. Calculer M^2 et interpréter le coefficient (M^2)_{1,3}.

Indice : Calcule M^2 en multipliant M par elle-même. Le coefficient (M^2)_{i,j} donne le nombre de chemins de longueur 2 de s_i à s_j.

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^k)_{i,j} = nombre de chemins de longueur exactement k allant de i à j. Pourquoi ? Parce que (M^2)_{i,j} = _r m_{i,r} m_{r,j} : 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^2 est la somme des lignes de M désignées par les 1 de la ligne i. Donc : ligne 1 de M^2 = ligne 2 de M · ligne 2 de M^2 = ligne 3 de M · ligne 3 de M^2 = ligne 1 de M
3. Étape 3 : On recopie ces trois lignes dans le bon ordre :

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

4. Étape 4 : Interprétation. (M^2)_{1,3} = 1 : il existe exactement un chemin de longueur 2 de s_1 à s_3.
5. Étape 5 : On peut l'exhiber, ce qui vérifie tout d'un coup :

   s_1 s_2 s_3 m_{1,2} = 1 et m_{2,3} = 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^2 ne compte QUE la longueur exacte : (M^2)_{1,3} = 1 ne dit pas « il y a un chemin de s_1 à s_3 » mais « il y en a un de longueur 2 ». Pour savoir s'il en existe un de longueur quelconque, il faut sommer M + M^2 + — 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^{k+1} = somme des lignes de M^k 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é.