Compter les chaînes d’un graphe avec les puissances de la matrice d’adjacence
Créez un compte gratuit pour suivre votre avancement et reprendre où vous avez laissé.
Créer un compteMéthode
Pour compter le nombre de chaînes d'une longueur donnée entre deux sommets d'un graphe :
- Étape 1 : construire la matrice d'adjacence $M$ du graphe en fixant un ordre sur les sommets.
- Étape 2 : calculer $M^k$, où $k$ est la longueur des chaînes recherchées (à la main pour $k$ petit, à la calculatrice sinon).
- Étape 3 : le coefficient $(M^k)_{i,j}$ situé à la $i$-ème ligne et la $j$-ème colonne donne le nombre de chaînes de longueur exactement $k$ reliant le sommet $i$ au sommet $j$.
- Étape 4 : pour compter les chaînes de longueur au plus $k$, additionner les coefficients correspondants des matrices $M, M^2, \dots, M^k$.
Chaînes de longueur 2
On considère le graphe ci-dessous (sommets dans l'ordre $A, B, C, D$). On cherche le nombre de chaînes de longueur $2$ reliant $A$ à $C$.
Étape 1 : La matrice d'adjacence est :
Étape 2 : On calcule $M^2 = M \times M$.
Pour le coefficient $(M^2)_{1,3}$ ligne $A$, colonne $C$, on multiplie la ligne $A$ par la colonne $C$ :
En procédant de même pour tous les coefficients :
Étape 3 : Le coefficient $(M^2)_{1,3}$ vaut $2$. Il y a donc $2$ chaînes de longueur $2$ reliant $A$ à $C$.
Vérification graphique : ces deux chaînes sont $A - B - C$ et $A - D - C$, ce qui est bien le cas sur le graphe.
Chaînes de longueur au plus 2
Avec le même graphe, on cherche le nombre de chaînes de longueur au plus $2$ reliant $B$ à $D$.
Étape 4 : On additionne les coefficients de la position $(B, D)$ dans $M$ et dans $M^2$, c'est-à-dire ligne $2$, colonne $4$ :
Il y a donc $3$ chaînes de longueur au plus $2$ reliant $B$ à $D$ :
- Une chaîne de longueur $1$ : $B - D$ (l'arête diagonale).
- Deux chaînes de longueur $2$ : $B - A - D$ et $B - C - D$.
Remarque
Pour des longueurs $k \geqslant 3$, le calcul à la main devient pénible : utiliser la calculatrice (mode matrices) ou un logiciel de calcul formel. Sur Numworks ou TI : entrer $M$ dans la mémoire matricielle, puis taper $\text{[A]}^k$.
Attention
Les « chaînes » comptées par $M^k$ sont des suites de sommets reliés par des arêtes, pas nécessairement des chaînes simples : un même sommet ou une même arête peut être emprunté plusieurs fois dans la chaîne.
Ainsi, dans l'exemple précédent, $A - B - A$ est une chaîne de longueur $2$ reliant $A$ à lui-même, qui contribue au coefficient $(M^2)_{1,1} = 2$.