Les puissances de la matrice comptent les chemins

1. Avec $M$ la matrice du chapitre ($0\to 1$, $0\to 2$, $1\to 3$, $3\to 2$), mesuré :

$$M^2=\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),M^3=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right),M^4=0.$$

On lit $(M^2{)}_{0,3}=1$ : il y a exactement un chemin de longueur $2$ de $0$ à $3$, à savoir $0\to 1\to 3$. Et $(M^3{)}_{0,2}=1$ : le chemin $0\to 1\to 3\to 2$. Vérifié indépendamment par énumération de tous les chemins.

2. $M^k=0$ signifie qu'il n'existe aucun chemin de longueur $k$. Ici $M^4=0$ : le plus long chemin du graphe a trois arcs.

Et c'est un critère d'acyclicité. Si le graphe contenait un cycle, on pourrait le parcourir autant de fois qu'on veut, donc il existerait des chemins de toute longueur, et aucune puissance de $M$ ne serait nulle. Réciproquement, dans un graphe sans circuit à $n$ sommets, un chemin ne peut répéter aucun sommet, donc sa longueur est au plus $n-1$ : $M^n=0$. D'où

$$\text{le graphe est acyclique}⟺M^n=0⟺M\text{ est nilpotente.}$$

Un graphe orienté est acyclique si et seulement si sa matrice d'adjacence est nilpotente — un fait algébrique pour un fait combinatoire, et l'un des plus jolis ponts entre les deux.

3. Le cas non orienté. La matrice $A$ est alors symétrique, et

$$(A^2{)}_{u,u}=\sum _w{A}_{u,w}{A}_{w,u}=\sum _w{A}_{u,w}^2=\sum _w{A}_{u,w}=d(u).$$

La diagonale de $A^2$ est la suite des degrés : un aller-retour $u\to w\to u$ est un chemin de longueur $2$, et il y en a autant que de voisins. Mesuré sur un graphe à $5$ sommets et $6$ arêtes : degrés $(2,3,3,3,1)$, diagonale de $A^2$ identique, et somme $12=2m$.

Pour $A^3$, un coefficient diagonal $(A^3{)}_{u,u}$ compte les chemins fermés de longueur $3$ partant de $u$ : ce sont exactement les triangles passant par $u$, chacun compté deux fois — une par sens de parcours. En sommant sur $u$, chaque triangle est de plus compté trois fois, une par sommet de départ. Donc

$$\#\{\text{triangles}\}=\frac{\mathrm{Tr}(A^3)}{6}.$$

Mesuré : $\mathrm{Tr}(A^3)=12$, donc $2$ triangles — et l'énumération directe donne bien $\{0,1,2\}$ et $\{1,2,3\}$.

Ce que cela coûte, et pourquoi on ne fait pas toujours ainsi. Compter les triangles par $\mathrm{Tr}(A^3)$ demande deux produits matriciels, soit $\Theta (n^3)$ — et $\Theta (n^2)$ de mémoire, donc impraticable sur un graphe creux de $10^7$ sommets. Le parcours des listes d'adjacence les compte en $O(m^{3/2})$, ce qui est bien meilleur dès que le graphe est creux. Une formule élégante n'est pas un algorithme, et le choix de la représentation continue de décider — c'est la remarque du chapitre sur Dijkstra et Floyd-Warshall.