Université de Paris Sud - Orsay Compléments de géométrie, 2016-2017
Les matrices d’adjacence : mode d’emploi
Étant donné un graphe, sa matrice d’adjacence permet de répondre, entre autres, aux questions suivantes :
• Combien y a-t-il de chemins de longueur 4 du sommet A au sommet B ?
• Combien y a-t-il de chemins de longueur 7 ?
• Combien y a-t-il de cycles de longueur 6 ?
La résolution d’un tel problème va typiquement passer par les trois étapes suivantes :
• Écrire la matrice M d’adjacence du graphe.
• Élever cette matrice à la puissance convenable, par exemple M 4 .
• Lire dans la matrice M 4 la solution du problème.
Suivant le problème, il peut très bien y avoir des étapes supplémentaires, comme par exemple traduire un problème concret en termes
de graphes. Nous donnons par la suite deux exemples de problèmes suivant ce schéma1 .
Un exemple simple
É NONCÉ
On se donne le graphe G suivant :
B C D
A E H
F G
Combien y a-t-il de cycles de longueur 6 de A à E ? Combien y a-t-il de cycles de longueur 6 ?
S OLUTION
On écrit tout d’abord la matrice d’adjacence du graphe G. En ordonnant les lignes de A à H dans l’ordre alphabétique, on obtient la
matrice :
0 1 0 0 0 1 0 0
1 0 1 0 1 1 0 0
0 1 0 1 1 0 1 0
0 0 1 0 0 0 1 1
M := 0 1 1 0 0 1 0 0 .
1 1 0 0 0 0 1 0
0 0 1 1 0 1 0 1
0 0 0 1 0 0 1 0
On s’intéresse tout d’abord aux chemins de longueur 6 de A à E. Pour cela, il faut élever la matrice M à la puissance 6. Heureusement,
un ordinateur peut faire le calcul à notre place (il va sans dire que l’on ne demandera à un étudiant de calculer à la main la puissance
sixième d’une matrice 8 par 8 !). On obtient :
110 176 162 108 161 160 157 67
176 317 273 201 271 276 280 117
162 273 346 201 232 329 238 166
6
108 201 201 164 176 185 209 104
M = .
161 271 232 176 246 227 255 100
160 276 329 185 227 328 217 148
157 280 238 209 255 217 298 118
67 117 166 104 100 148 118 89
1 Ces exemples sont étudiés en détail ; ce ne sont pas des exemples de rédaction !
1
Université de Paris Sud - Orsay Compléments de géométrie, 2016-2017
Un théorème du cours affirme que, dans un graphe (orienté ou non) de matrice d’adjacence M, le nombre de chemins de longueur n
d’un sommet s à un sommet t est égal à (Mn )st , c’est-à-dire au coefficient de Mn sur la ligne s et sur la colonne t.
Ici, le nombre de chemins de longueur 6 de A à E est donc égal à (M 6 )AE , c’est-à-dire au coefficient en ligne 1 et colonne 5 de la
matrice ci-dessus. C’est le coefficient écrit en rouge. Il y a donc 161 chemins de longueur 6 de A à E.
Un cycle est un chemin dont le point de départ et d’arrivée coïncident. C’est donc un chemin qui part de A et qui arrive en A, ou bien qui
part de B et qui arrive en B, etc. Le nombre de cycles de longueur 6 qui partent de A et qui arrivent en A est égal à (M 6 )AA , soit 110.
Ceux qui partent de B et arrivent en B correspondent à (M 6 )BB , soit 317. On continue ainsi : on obtient les nombres sur la diagonale
bleue. Finalement, pour compter tous les cycles, quelque soit leur point de départ, il faut additionner tous ces coefficients. Il y a :
110 + 317 + 346 + 164 + 246 + 328 + 298 + 89 = 1898
cycles de longueur 6.
Un problème d’interprétation
É NONCÉ
Un nombre est dit élégant2 si la différence entre deux chiffres consécutifs est d’au plus 1. Combien y a-t-il de nombres élégants à 8
chiffres, dont les chiffres sont tous compris entre 0 et 4 (inclus) ?
S OLUTION
Ce problème pose une difficulté supplémentaire : il faut d’abord le traduire dans le langage des graphes.
On construit un nombre élégant en concaténant les chiffres un à un. Remarquons que :
• 0 est suivi de 0 ou 1 ;
• 1 est suivi de 0, 1 ou 2 ;
• 2 est suivi de 1, 2 ou 3 ;
• 3 est suivi de 2, 3 ou 4 ;
• 4 est suivi de 3 ou 4.
On construit le graphe dont les sommets sont les chiffres de 0 à 4, et tel qu’il y a une arête entre deux sommets si la différence entre les
sommets vaut au plus 1. On obtient le graphe suivant :
Un nombre élégant à 8 chiffres correspond à une suite de 8 sommets reliés par des arêtes, soit 8 sommets qui forment un chemin. Mais,
comme il y a 8 sommets, il n’y a besoin que de 7 arêtes pour parcourir le chemin ! Un nombre élégant à 8 chiffres correspond donc à un
chemin de longueur 7 sur le graphe ci-dessus. L’énoncé peut donc se reformuler de la façon suivante :
Combien y a-t-il de chemins de longueur 7 dans le graphe ci-dessus ?
C’est une question à laquelle on peut répondre en faisant intervenir la matrice d’adjacence du graphe. En classant les sommets par ordre
croissant, on obtient la matrice :
1 1 0 0 0
1 1 1 0 0
M := 0 1 1 1 0 .
0 0 1 1 1
0 0 0 1 1
2 Par exemple, 123323454 est élégant, et 12354 ne l’est pas.
2
Université de Paris Sud - Orsay Compléments de géométrie, 2016-2017
Pour obtenir le nombre de chemins de longueur 7, il faut élever la matrice M à la puissance 7. L’ordinateur calcule :
127 196 189 132 63
196 316 328 252 132
7
M := 189 328 379 328 189 .
132 252 328 316 196
63 132 189 196 127
Il y a par exemple 127 nombres élégants à 8 chiffres qui commencent et finissent par 0 ; 252 nombres élégants à 8 chiffres qui commen-
cent par 1 et finissent par 3 ; 63 nombres élégants à 8 chiffres qui commencent par 0 et finissent par 4...
En additionnant tous les coefficients, on obtient la réponse attendue : il y a 5275 nombres élégants à 8 chiffres.
