Mathématiques Expertes · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel
Définitions et théorèmes
À tout graphe à n sommets (numérotés de 1 à n) on associe sa matrice d'adjacence M, carrée d'ordre n, définie par :
m_{i,j}=\begin{cases} 1 & \text{s'il existe une arête (ou un arc) de } i \text{ vers } j \\ 0 & \text{sinon.}\end{cases}
Pour un graphe non orienté, M est symétrique : m_{i,j}=m_{j,i}, soit M^{\mathrm{T}}=M.
Pour un graphe orienté, M n'est en général pas symétrique.
Dans un graphe non orienté simple, le degré du sommet i est la somme des coefficients de sa ligne.
Théorème (puissances de la matrice d'adjacence). Pour tout entier k\ge 1, le coefficient (i,j) de M^k est égal au nombre de chaînes (ou chemins, si orienté) de longueur exactement k reliant le sommet i au sommet j.
En particulier (M^2)_{i,j}=\sum_k m_{i,k}m_{k,j} compte les chemins à un sommet intermédiaire.
Formules
(M^k)_{i,j}= nombre de chemins de longueur k de i à j.
Graphe non orienté simple : \deg(i)=\sum_j m_{i,j}=(M^2)_{i,i}.
M^{k+1}=M\times M^k (calcul par produit).
Méthodes type bac
Construire M : numéroter les sommets, remplir avec 0 et 1, vérifier la symétrie si le graphe est non orienté.
Compter les chemins : calculer M^k (souvent à la calculatrice) et lire le coefficient (i,j).
Interpréter : énumérer concrètement les chaînes correspondant au coefficient pour vérifier.
Lire les degrés : sommer chaque ligne de M (graphe non orienté).
Pièges
(M^k)_{i,j} compte les chemins de longueur exactement k, pas « au plus k ».
Pour un graphe orienté, l'ordre i\to j compte : m_{i,j}\neq m_{j,i} en général.
Une chaîne de longueur 2 peut repasser par le sommet de départ : (M^2)_{i,i} n'est pas forcément nul.
Ne pas confondre matrice d'adjacence (graphe) et matrice de transition (graphe probabiliste, à coefficients de probabilités).
Pour l'épreuve
Le résultat clé est l'interprétation des coefficients de M^k comme nombres de chemins de longueur k. La calculatrice donne M^k ; l'écrit attend la construction soignée de M et l'interprétation des coefficients, souvent illustrée en énumérant les chemins. Veille à préciser l'ordre dans lequel tu numérotes les sommets : tout le reste en dépend, et une erreur de numérotation rend la matrice fausse dès le départ. Pour vérifier un coefficient de M^2, le réflexe efficace consiste à chercher les sommets intermédiaires reliés à la fois au point de départ et au point d'arrivée, ce qui correspond exactement à la somme \sum_k m_{i,k}m_{k,j} et permet de recouper le résultat de la machine.