Compétence · Terminale TE.MATR.GADJ.01 Niveau : Moyen

Compter les chaînes d'un graphe avec les puissances de sa matrice d'adjacence

Le coefficient (i, j) de Aⁿ est le nombre de chaînes de longueur n qui relient le sommet i au sommet j ; le démontrer par récurrence et l'appliquer à un réseau ou à un graphe complet.

Chapitre : Graphes et chaînes de Markov Filière : Term Maths Expertes Temps de maîtrise : ~60 min

Le cours

Compter les chaînes de longueur $n$~2 min

À retenir — chaînes et puissances de la matrice d'adjacence

Soit $A$ la matrice d'adjacence d'un graphe (orienté ou non). Pour tout $n\geq1$, le coefficient $(i,j)$ de $A^n$ est le nombre de chaînes de longueur $n$ allant du sommet $i$ au sommet $j$.

Démonstration exigible — nombre de chaînes de longueur $n$

Par récurrence sur $n$. Notons $c_n(i,j)$ le nombre de chaînes de longueur $n$ de $i$ à $j$.
Initialisation. Une chaîne de longueur $1$ de $i$ à $j$ est une arête (ou un arc) de $i$ à $j$ : $c_1(i,j)=a_{ij}$, coefficient de $A^1$.
Hérédité. Supposons que, pour tout couple $(i,k)$, $c_n(i,k)$ soit le coefficient $(i,k)$ de $A^n$. Une chaîne de longueur $n+1$ de $i$ à $j$ est constituée d'une chaîne de longueur $n$ de $i$ à un sommet $k$, suivie d'une arête de $k$ à $j$. Pour $k$ fixé il y a $c_n(i,k)\times a_{kj}$ telles chaînes, et les différentes valeurs de $k$ donnent des chaînes distinctes. Donc $$c_{n+1}(i,j)=\sum_{k=1}^{N}c_n(i,k)\,a_{kj}=\sum_{k=1}^{N}(A^n)_{ik}\,a_{kj}=(A^nA)_{ij}=(A^{n+1})_{ij}.$$ La propriété est héréditaire, donc vraie pour tout $n\geq1$.

Exemple

Dans $G$ : le coefficient $(A^2)_{AD}=2$ : deux chaînes de longueur $2$ de A à D (A-B-D et A-C-D). $(A^2)_{CC}=4$ : quatre chaînes fermées de longueur $2$ en C, une par voisin (aller-retour) : c'est le degré de C. $(A^3)_{AE}=3$ : A-B-C-E, A-C-D-E, A-B-D-E. On a utilisé np.linalg.matrix_power(A, 3).

Exemple

Chaînes eulériennes (problème possible du programme). Une chaîne qui emprunte chaque arête exactement une fois est eulérienne. Théorème d'Euler : un graphe connexe admet une chaîne eulérienne si et seulement s'il a $0$ ou $2$ sommets de degré impair ; s'il en a $0$, la chaîne peut être fermée (cycle eulérien) ; s'il en a $2$, elle les a pour extrémités. Dans $G$, seuls B et D sont de degré impair : B-A-C-B-D-C-E-D convient. À Königsberg (sept ponts, quatre quartiers de degrés $3,3,3,5$) : impossible.

Conçu et validé par Laurent Jacquet, professeur de mathématiques. Qui conçoit les cours ?

Entraîne-toi sur ce cours

Avec un compte gratuit : les QCM et ta Konfiance après chaque question, et le sentier complet d'un chapitre au choix, rappels et épreuve compris.

Créer mon compte gratuit

Déjà inscrit ? Se connecter

Pour aller plus loin

Maîtrise cette compétence avec Konfia

Coach personnel, corrigés détaillés, missions hebdomadaires ciblées sur tes lacunes. Un accompagnement quotidien pour le prix d'un café par mois.

Découvrir l'accompagnement — dès 4,99 €/mois