Puissances de la matrice d'adjacence et chemins de longueur p

Si M est la matrice d'adjacence d'un graphe, le coefficient ligne i, colonne j de la puissance entière Mᵖ = M × M × … × M est le nombre de chemins de longueur p qui vont du sommet i au sommet j. La puissance booléenne M^[p], calculée avec la règle 1 + 1 = 1, dit seulement s'il existe au moins un tel chemin (1) ou non (0). Ce chapitre explique pourquoi, montre comment calculer ces puissances à la main et à la machine, et comment les interpréter : c'est la question de matrices la plus fréquente des exercices de graphes de l'E3.

Rappel : le produit de deux matrices

Le produit de deux matrices carrées A et B de même taille n est la matrice C = A × B dont le coefficient ligne i, colonne j est le produit de la ligne i de A par la colonne j de B : on multiplie les coefficients deux à deux et on additionne.

cᵢⱼ = aᵢ₁ × b₁ⱼ + aᵢ₂ × b₂ⱼ + … + aᵢₙ × bₙⱼ

Par exemple, si la ligne i de A est (1 0 1) et la colonne j de B est (1 1 1) lue de haut en bas, alors cᵢⱼ = 1 × 1 + 0 × 1 + 1 × 1 = 2. Le produit de matrices n'est pas commutatif en général, mais les puissances d'une même matrice ne posent pas ce problème : M² = M × M, M³ = M² × M = M × M², etc. Le calcul matriciel complet est dans le cours de matrices.

Pourquoi M² compte les chemins de longueur 2

Prenons la matrice M du graphe G du ticket (sommets dans l'ordre A, B, C, D, E) :

Calculons le coefficient de M² à la ligne C, colonne C : la ligne C de M, (0 0 1 1 0), multipliée par la colonne C de M, (0 1 1 1 0).

(M²)_CC = 0 × 0 + 0 × 1 + 1 × 1 + 1 × 1 + 0 × 0 = 2.

Chaque terme correspond à un sommet intermédiaire k : le terme mₖ = m_Ck × m_kC vaut 1 exactement quand il y a un arc de C vers k et un arc de k vers C, c'est-à-dire quand (C, k, C) est un chemin de longueur 2. Ici, deux termes valent 1 : k = C (le chemin (C, C, C), deux fois la boucle) et k = D (le chemin (C, D, C)). La somme compte ces chemins.

En faisant ce calcul pour toutes les cases, on obtient M² :

Lecture de quelques coefficients :

• (M²)_AA = 1 : un seul chemin de longueur 2 de A vers A, (A, B, A) ;
• (M²)_BE = 1 : un seul chemin de longueur 2 de B vers E, (B, A, E) ;
• (M²)_AE = 0 : aucun chemin de longueur 2 de A vers E (A → B → ? ne mène pas en E, et E n'a pas de successeur) ;
• la ligne E reste nulle : aucun chemin ne part de E.

Le théorème : Mᵖ compte les chemins de longueur p

Le raisonnement se prolonge : un chemin de longueur 3 de i vers j, c'est un chemin de longueur 2 de i vers un sommet k, suivi d'un arc de k vers j. Le coefficient (M³)ᵢⱼ = (M² × M)ᵢⱼ additionne, pour chaque k, le nombre de chemins de longueur 2 de i vers k multiplié par 1 ou 0 selon que l'arc (k, j) existe : il compte donc les chemins de longueur 3.

Pour le graphe G, M³ = M² × M donne :

Vérifions un coefficient à la main. (M³)_BC est le produit de la ligne B de M², (0 1 1 1 1), par la colonne C de M, (0 1 1 1 0) : 0 + 1 + 1 + 1 + 0 = 3. Il y a donc 3 chemins de longueur 3 de B vers C. Les voici : (B, A, B, C), (B, C, C, C) et (B, C, D, C).

Et (M³)_CC = 3 : trois circuits de longueur 3 passent par C, à savoir (C, C, C, C), (C, C, D, C) et (C, D, C, C).

Le calcul booléen

Souvent, on ne veut pas savoir combien de chemins existent, mais seulement s'il en existe. On calcule alors avec l'algèbre de Boole, où les seules valeurs sont 0 et 1 et où l'on utilise deux opérations :

La seule différence avec le calcul ordinaire est 1 ⊕ 1 = 1 : « vrai ou vrai » reste vrai. Les manuels écrivent aussi + et ×, ou ∨ et ∧, en précisant qu'on calcule en booléen. C'est le calcul de la logique booléenne, appliqué aux matrices.

Somme booléenne de deux matrices. On fait la somme booléenne case par case : la case vaut 1 si l'une au moins des deux matrices a un 1 à cet endroit.

Produit booléen de deux matrices. On fait le produit ligne × colonne, mais avec ⊗ et ⊕ : la case (i, j) vaut 1 dès qu'au moins un terme aᵢₖ ⊗ bₖⱼ vaut 1.

Les puissances booléennes M^[p]

La puissance booléenne M^[p] est le produit booléen de p matrices égales à M. Son coefficient ligne i, colonne j vaut :

• 1 s'il existe au moins un chemin de longueur p de i vers j ;
• 0 s'il n'en existe aucun.

Pour le graphe G, M^[2] et M^[3] s'obtiennent en remplaçant par 1 les coefficients non nuls de M² et M³ :

La puissance booléenne perd une information (le nombre de chemins), mais elle se calcule plus vite et reste lisible même quand les nombres de chemins deviennent grands.

Lister les chemins de longueur p

La matrice dit combien de chemins existent, pas lesquels. Pour les écrire, on part du sommet de départ et on construit l'arbre des chemins : à chaque étape, on remplace chaque chemin par ses prolongements possibles, avec le tableau des successeurs.

Exemple : les chemins de longueur 3 qui partent de C (successeurs : A → B, E ; B → A, C ; C → C, D ; D → C, E ; E → aucun).

• Longueur 1 : (C, C), (C, D).
• Longueur 2 : (C, C, C), (C, C, D), (C, D, C), (C, D, E).
• Longueur 3 : (C, C, C, C), (C, C, C, D), (C, C, D, C), (C, C, D, E), (C, D, C, C), (C, D, C, D). Le chemin (C, D, E) ne se prolonge pas : E n'a pas de successeur.

On trouve 6 chemins de longueur 3 partant de C : 3 arrivent en C, 2 en D, 1 en E. C'est exactement la ligne C de M³, (0 0 3 2 1). Faire ce recoupement est la meilleure vérification de ton calcul matriciel.

C'est aussi l'algorithme que demande le programme pour « obtenir les chemins de longueur p » : on calcule les puissances successives M, M², …, Mᵖ (ou on prolonge les chemins un arc à la fois), en réutilisant à chaque étape le résultat de l'étape précédente.

Vérifier avec la calculatrice ou Python

Les calculatrices autorisées à l'examen (en mode examen) ont un éditeur de matrices : on saisit M une fois, puis on calcule M² ou M³ avec la touche de puissance, comme pour un nombre. Le résultat est la puissance entière ; pour la puissance booléenne, remplace toi-même chaque coefficient non nul par 1.

En Python, sans bibliothèque :

def produit(A, B):
    """Produit ordinaire de deux matrices carrées."""
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n)) for j in range(n)]
            for i in range(n)]

def produit_booleen(A, B):
    """Produit booléen : 1 dès qu'un terme A[i][k] et B[k][j] vaut 1."""
    n = len(A)
    return [[1 if any(A[i][k] == 1 and B[k][j] == 1 for k in range(n)) else 0
             for j in range(n)] for i in range(n)]

def puissance(M, p, produit=produit):
    """M à la puissance p (p >= 1), ordinaire ou booléenne."""
    R = M
    for _ in range(p - 1):
        R = produit(R, M)
    return R

M = [[0, 1, 0, 0, 1],
     [1, 0, 1, 0, 0],
     [0, 0, 1, 1, 0],
     [0, 0, 1, 0, 1],
     [0, 0, 0, 0, 0]]

print(puissance(M, 3)[1])                    # [1, 0, 3, 1, 1] : ligne B de M³
print(puissance(M, 3, produit_booleen)[1])   # [1, 0, 1, 1, 1] : ligne B de M^[3]

Avec la bibliothèque NumPy, numpy.linalg.matrix_power(M, 3) calcule directement M³.

Ce que cela donne en informatique

• Réseaux sociaux : si M est la matrice « suit », (M²)ᵢⱼ compte les comptes que i suit et qui suivent j. C'est le principe des suggestions « suivi par des personnes que vous suivez ».
• Relais de messages : dans un réseau de relais, (Mᵖ)ᵢⱼ est le nombre d'acheminements possibles d'un message de i vers j en exactement p sauts.
• Analyse de liens web : les algorithmes de classement des pages s'appuient sur des produits répétés d'une matrice dérivée de la matrice d'adjacence du web.
• Bases de données : une jointure d'une table de relations avec elle-même calcule les liens de longueur 2, comme un produit de matrices.

Exercices