Compter les chemins de longueur donnée

Le code.

import numpy as np

A = np.array([[0, 1, 0, 0],
              [1, 0, 1, 1],
              [0, 1, 0, 1],
              [0, 1, 1, 0]])

def puissance(A, k):
    n = np.shape(A)[0]
    P = np.eye(n)                 # matrice identite : A puissance 0
    for _ in range(k):
        P = np.dot(P, A)
    return P

print(puissance(A, 2))

Le résultat.

$$A^2=\left(\begin{array}{cccc}1& 0& 1& 1\\ 0& 3& 1& 1\\ 1& 1& 2& 1\\ 1& 1& 1& 2\end{array}\right)$$

Vérification à la main de trois coefficients.

• $(A^2{)}_{0,0}=1$ : le seul chemin de longueur $2$ de $0$ à $0$ est $0\to 1\to 0$, puisque $1$ est l'unique voisin de $0$.
• $(A^2{)}_{1,1}=3$ : les chemins $1\to 0\to 1$, $1\to 2\to 1$ et $1\to 3\to 1$ — le sommet $1$ a trois voisins.
• $(A^2{)}_{0,1}=0$ : aucun chemin de longueur $2$ ne joint $0$ à $1$. Ils sont voisins, donc à distance $1$ ; un chemin de longueur $2$ devrait repasser par un sommet, or le seul voisin de $0$ est $1$ lui-même.

Pourquoi la formule est vraie. Par définition du produit matriciel,

$$(A^2{)}_{i,j}=\sum _{m=0}^{n-1}{A}_{i,m}{A}_{m,j}.$$

Chaque terme vaut $1$ si $m$ est voisin à la fois de $i$ et de $j$, et $0$ sinon : la somme compte donc exactement les sommets intermédiaires $m$ réalisant un chemin $i\to m\to j$. Le raisonnement se poursuit par récurrence sur $k$ : $A^{k+1}=A^{k}A$, et l'on décompose un chemin de longueur $k+1$ en un chemin de longueur $k$ suivi d'une arête.

Deux points de vigilance. D'abord, np.dot(P, A) est le produit matriciel — l'opération P * A de numpy multiplierait coefficient par coefficient, ce qui n'a rien à voir et ne provoque aucune erreur. Ensuite, « chemin » s'entend ici au sens large : un même sommet peut être revisité, comme dans $1\to 0\to 1$.