Un graphe décrit des objets et leurs relations. Sa matrice d'adjacence transforme cette structure en calcul, ce qui permet de compter des parcours de longueur fixée.
La convention d'orientation doit être annoncée. Inverser lignes et colonnes transpose la matrice et change l'interprétation des coefficients.
Décrire un graphe
Sommets et arêtes
Un graphe est formé de sommets reliés par des arêtes. Dans un graphe orienté, chaque liaison possède un sens et s'appelle un arc.
Une chaîne suit des arêtes successives ; un chemin suit les orientations. Sa longueur est le nombre d'arêtes ou d'arcs parcourus, pas le nombre de sommets écrits.
Lire degrés et voisinages
Dans un graphe non orienté, le degré d'un sommet compte les arêtes incidentes. Dans un graphe orienté, on distingue degré entrant et degré sortant. La somme des degrés d'un graphe non orienté vaut deux fois le nombre d'arêtes.
Deux sommets sont voisins lorsqu'une arête les relie. Un graphe est complet lorsque toute paire de sommets distincts est voisine, et connexe lorsqu'une chaîne relie n'importe quelle paire de sommets.
Lemme des poignées de main
Dans tout graphe non orienté fini, la somme des degrés des sommets est paire.
Construire la matrice d’adjacence
Matrice d’adjacence
Après avoir ordonné les sommets, le coefficient compte les arcs allant du sommet i vers le sommet j.
Pour un graphe simple non orienté, la matrice est symétrique. Une boucle apparaît sur la diagonale. L'ordre des sommets fait partie des données et doit rester identique pendant tous les calculs.
Interpréter les puissances
Comptage des parcours
Le coefficient de compte les chemins de longueur n allant du sommet i au sommet j.
La multiplication matricielle additionne les possibilités obtenues en passant par chaque sommet intermédiaire. Cette interprétation explique le produit au lieu de le réduire à une recette.
Exemple sur un triangle complet
Pour trois sommets tous reliés deux à deux et sans boucle, la matrice d'adjacence possède des zéros sur la diagonale et des uns ailleurs. Dans son carré, chaque coefficient diagonal vaut 2 : depuis un sommet, deux parcours de longueur 2 y reviennent en passant par l'un des deux autres sommets. Chaque coefficient hors diagonale vaut 1, car un unique sommet intermédiaire permet de rejoindre l'autre extrémité sans boucle.
Calculer avec des matrices
Deux matrices s'additionnent seulement si elles ont les mêmes dimensions. Le produit AB existe lorsque le nombre de colonnes de A égale le nombre de lignes de B. En général AB et BA sont différents, voire l'un des deux seulement est défini.
| Calcul | Interprétation |
|---|---|
| A² | parcours de longueur 2 |
| A³ | parcours de longueur 3 |
| somme d'une ligne | degré sortant dans un graphe simple |
| transposée | orientation inversée |
Décider si un parcours eulérien existe
Dans un graphe non orienté connexe, un cycle eulérien existe lorsque tous les sommets sont de degré pair. Une chaîne eulérienne ouverte existe lorsqu'exactement deux sommets sont de degré impair ; ils en sont alors les extrémités.
Le contrôle porte donc à la fois sur la connexité et sur les degrés. Une liste de degrés ne suffit pas si le graphe peut être séparé en plusieurs composantes.
Modéliser sans ambiguïté
Erreur fréquente : compter les sommets d'une chaîne au lieu de ses arêtes décale toutes les longueurs d'une unité.
Contrôle utile : dessiner le graphe correspondant à une petite matrice contrôle la convention ligne vers colonne.
Les matrices de transition pondèrent les arcs par des probabilités.
La modélisation par graphes et matrices appartient à le programme officiel de mathématiques expertes en Terminale.