Compter les chemins d'un graphe

Stratégie : une récurrence de dénombrement, puis l'identité $J^2=3J$ pour tout calculer.

Ici $M=J-I_3=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 1\\ 1& 1& 0\end{array}\right)$ : chaque sommet est relié aux deux autres et pas à lui-même.

1) Le comptage, par récurrence sur $k$. Notons $c_k(i,j)$ le nombre de chemins de longueur $k$ de $i$ vers $j$. Pour $k=1$, un chemin de longueur $1$ est une arête : $c_1(i,j)=M_{ij}$, l'énoncé est vrai. Supposons ${\left(M^k\right)}_{ij}=c_k(i,j)$ et considérons un chemin de longueur $k+1$ de $i$ à $j$. Il se décompose de façon unique en : un chemin de longueur $k$ de $i$ vers un sommet intermédiaire $m$, suivi d'une arête de $m$ vers $j$. En classant les chemins selon ce sommet $m$ :

$$c_{k+1}(i,j)=\sum _{m=1}^3{c}_k(i,m)M_{mj}=\sum _{m=1}^3{\left(M^k\right)}_{im}{M}_{mj}={\left(M^{k+1}\right)}_{ij}.$$

⚠️ Le point délicat est l'unicité de la coupure. On additionne les cas $m=1,2,3$ sans rien compter deux fois parce que chaque chemin détermine sans ambiguïté son avant-dernier sommet. C'est exactement ce qui fait de la définition du produit matriciel — une somme sur l'indice intermédiaire — l'outil du dénombrement.

2) Les puissances. On utilise $J^2=3J$ (chaque coefficient de $J^2$ vaut $1+1+1$) :

$$M^2=(J-I_3{)}^2=J^2-2J+I_3=3J-2J+I_3=J+I_3=\left(\begin{array}{ccc}2& 1& 1\\ 1& 2& 1\\ 1& 1& 2\end{array}\right).$$

(Le binôme est ici légitime : $J$ et $I_3$ commutent.) Lecture : de $1$ vers $1$ en deux pas, il y a $2$ chemins — aller en $2$ et revenir, ou aller en $3$ et revenir ; de $1$ vers $2$ en deux pas, il y en a $1$ — passer par $3$. ✔

$$M^3=M^{2}M=(J+I_3)(J-I_3)=J^2-I_3=3J-I_3=\left(\begin{array}{ccc}2& 3& 3\\ 3& 2& 3\\ 3& 3& 2\end{array}\right).$$

Lecture : de $1$ vers $1$ en trois pas, $2$ chemins — le triangle parcouru dans un sens ou dans l'autre ; de $1$ vers $2$ en trois pas, $3$ chemins. ✔

3) La formule générale. Toute puissance de $M$ est de la forme $M^k={\alpha }_{k}J+{\beta }_k{I}_3$, car cette forme est stable :

$$M^{k+1}=\left({\alpha }_{k}J+{\beta }_k{I}_3\right)(J-I_3)={\alpha }_k(3J)-{\alpha }_{k}J+{\beta }_{k}J-{\beta }_k{I}_3=\left(2{\alpha }_k+{\beta }_k\right)J-{\beta }_k{I}_3.$$

D'où ${\beta }_{k+1}=-{\beta }_k$ et ${\alpha }_{k+1}=2{\alpha }_k+{\beta }_k$, avec ${\alpha }_1=1$ et ${\beta }_1=-1$. La première donne ${\beta }_k=(-1{)}^k$ ; la seconde devient ${\alpha }_{k+1}=2{\alpha }_k+(-1{)}^k$, dont la solution est ${\alpha }_k=\frac{2^k-(-1{)}^k}{3}$ (récurrence immédiate). Finalement

$$\boxed{M^k=\frac{2^k-(-1{)}^k}{3}J+(-1{)}^k{I}_3,}$$

soit, coefficient par coefficient : $\frac{2^k+2(-1{)}^k}{3}$ sur la diagonale, et $\frac{2^k-(-1{)}^k}{3}$ ailleurs.

Contrôles numériques. Pour $k=1$ : diagonale $\frac{2-2}{3}=0$ ✔, hors diagonale $\frac{2+1}{3}=1$ ✔. Pour $k=2$ : $\frac{4+2}{3}=2$ et $\frac{4-1}{3}=1$ ✔. Pour $k=3$ : $\frac{8-2}{3}=2$ et $\frac{8+1}{3}=3$ ✔. Pour $k=4$ : $6$ et $5$, ce que confirme le calcul direct de $M^4$. La formule a été vérifiée jusqu'à $k=10$.

Un contrôle qui vaut preuve. Depuis un sommet fixé, on a deux choix à chaque pas, donc $2^k$ chemins de longueur $k$ en tout. Or la somme d'une ligne de $M^k$ vaut

$$\frac{2^k+2(-1{)}^k}{3}+2\times \frac{2^k-(-1{)}^k}{3}=\frac{3\times 2^k}{3}=2^k.✓$$

Ce que l'exercice installe. La puissance d'une matrice d'adjacence compte. Le produit matriciel, avec sa somme sur l'indice intermédiaire, est littéralement l'outil du dénombrement des chemins — et c'est ainsi que l'on calcule sur les graphes, des réseaux sociaux aux moteurs de recherche.