Utiliser un chemin pour compter des enchaînements dans un réseau
Utiliser la notion de chemin (chaîne) dans un graphe orienté ou non orienté, et calculer à l'aide des puissances de la matrice d'adjacence le nombre de chemins de longueur donnée entre deux sommets.

Les points essentiels
- Un chemin de longueur k dans un graphe orienté est une suite de k arcs consécutifs : l'extrémité de chaque arc est l'origine du suivant. Sa longueur est le nombre d'arcs, comptés avec répétition.
- Dans un graphe non orienté, on parle de chaîne de longueur k : suite de k arêtes consécutives. Le vocabulaire diffère, mais le principe de calcul matriciel est le même.
Les mots à connaître
- Chemin (graphe orienté) / chaîne (graphe non orienté)
- Suite finie d'arcs (resp. d'arêtes) telle que l'extrémité de chacun est l'origine du suivant. Sa longueur est le nombre d'arcs (resp. d'arêtes) parcourus, un même arc pouvant être emprunté plusieurs fois.
- Matrice d'adjacence
- Matrice carrée A d'ordre n dont le coefficient a_ij est le nombre d'arcs (resp. d'arêtes) du sommet i vers le sommet j, les sommets étant rangés dans un ordre fixé (souvent alphabétique).
Un exemple pour comprendre
Graphe orienté de sommets 1, 2, 3 et d'arcs : 1→2, 1→3, 2→3, 3→1. Écrire A, calculer A^2 et donner le nombre de chemins de longueur 2 de 1 vers 1, puis les lister.
Lignes = origine, colonnes = arrivée : A = [[0,1,1],[0,0,1],[1,0,0]]. Calcul de A^2 ligne par ligne : ligne 1 = ligne2 + ligne3 de A = (0,0,1)+(1,0,0) = (1,0,1). Ligne 2 = ligne3 de A = (1,0,0). Ligne 3 = ligne1 de A = (0,1,1). Donc A^2 = [[1,0,1],[1,0,0],[0,1,1]]. Le coefficient (1 ; 1) vaut 1 : un seul chemin de longueur 2 de 1 vers 1, à savoir 1→3→1 (le chemin 1→2→? ne revient pas en 1 en un arc car il n'y a pas d'arc 2→1).

