Pourquoi une puissance de matrice compte-t-elle aussi les trajets avec répétition ?

Réponse courte

Une puissance de matrice d’adjacence compte aussi les trajets avec répétition, car chaque étape choisit un arc sans vérifier si ses sommets ont déjà été visités.

Comprendre

Le produit additionne les prolongements

Pour M², le coefficient (i ; j) est la somme des produits mᵢₖmₖⱼ sur tous les sommets intermédiaires k. Chaque terme compte un trajet de i à k puis de k à j. Le calcul vérifie les arcs de deux étapes, mais ne compare pas k à d’autres sommets déjà traversés. Il n’y a donc aucune règle qui écarte les retours.

Un retour compté

Dans le graphe non orienté formé de l’unique arête AB, le trajet A, B, A utilise deux fois la même arête et revient au sommet de départ. Le coefficient de ligne A et colonne A dans M² vaut 1, car le sommet intermédiaire B fournit précisément ce trajet.

Pourquoi cela reste vrai à toute puissance

Pour prolonger un trajet de longueur n en un trajet de longueur n + 1, le produit MⁿM examine son dernier arc depuis chaque sommet intermédiaire. Tous les prolongements valides sont additionnés, y compris ceux qui reviennent sur une étape antérieure. Pour compter des trajets sans répétition, il faut suivre cette contrainte séparément ; Mⁿ seul ne l’encode pas.

Exemples

  • Avec le seul arc non orienté AB, A, B, A est un trajet de longueur 2 ; le coefficient (A ; A) de M² vaut 1.
  • Dans la chaîne A—B—C, les trajets A, B, A, B et A, B, C, B ont tous deux longueur 3 et sont comptés par le coefficient (A ; B) de M³.

Pièges fréquents

  • Supposer qu’une puissance impose un trajet simple : le calcul ne mémorise pas les sommets déjà visités.
  • Confondre un retour compté dans M² avec une boucle présente au départ : A, B, A emprunte deux arêtes et ne crée pas d’arête A vers A.

Et maintenant ?

Questions proches

← Toutes les questions-réponses