Terminale · Mathématiques

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.

Aperçu gratuit
Illustration de la fiche « Utiliser un chemin pour compter des enchaînements dans un réseau »

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).

Première page de l’Essentiel : Utiliser un chemin pour compter des enchaînements dans un réseau
Ketty