Que compte un coefficient d’une puissance de matrice d’adjacence ?

Réponse courte

Pour une matrice d’adjacence M, le coefficient de ligne i et colonne j de Mⁿ compte les chemins de longueur n allant du sommet i au sommet j, en respectant l’orientation et avec répétitions autorisées.

Comprendre

Lire un coefficient

Fixe un ordre pour les sommets et utilise la même convention dans toute la matrice : ligne = départ, colonne = arrivée. Le coefficient (i ; j) de Mⁿ donne le nombre de successions de n arcs qui partent du sommet i et arrivent au sommet j. La longueur n désigne le nombre de liaisons parcourues, et non une distance géographique.

Exemple en deux étapes

Pour les arcs A vers B, B vers C et A vers C, dans l’ordre A, B, C, M = (0, 1, 1 ; 0, 0, 1 ; 0, 0, 0). Il existe un seul chemin de longueur 2 de A à C : A, B, C. Le coefficient de ligne A, colonne C dans M² vaut donc 1.

Répétitions permises

Le calcul compte toute succession valide, même si elle repasse par un sommet ou un arc. Dans le graphe non orienté réduit à l’arête AB, la case (A ; A) de M² vaut 1 : le trajet A, B, A revient au départ. Si l’énoncé interdit les répétitions, le coefficient de Mⁿ ne répond pas directement à cette contrainte.

Exemples

  • Avec A→B→C et A→C, il y a un chemin de longueur 2 de A vers C : A, B, C.
  • Dans le graphe non orienté à deux sommets reliés par AB, le coefficient (A ; A) de M² vaut 1, pour le retour A, B, A.

Pièges fréquents

  • Lire le coefficient de M au lieu de Mⁿ : M code les liaisons en une étape, Mⁿ celles en n étapes.
  • Écarter les trajets qui repassent par un sommet : les puissances comptent les répétitions, sauf contrainte supplémentaire explicitement traitée.

Et maintenant ?

Questions proches

← Toutes les questions-réponses