Un réseau de bus, un groupe d'amis, un tournoi : dès que tu étudies des objets et leurs liens, tu les représentes par des points reliés par des traits, c'est-à-dire par un graphe. Tu vas apprendre à le décrire, à modéliser une situation par un graphe, à le coder par une matrice et à compter ses chemins grâce aux puissances de cette matrice.
Graphe, sommets, arêtes
Un graphe est formé d'un ensemble fini de points, les sommets, et de liens entre certains d'entre eux, les arêtes. Ici, une arête relie toujours deux sommets distincts, et deux sommets sont reliés par au plus une arête. Seules comptent les paires de sommets reliées, pas la forme du dessin.
Exemple
Le graphe a pour sommets , , , et pour arêtes –, –, –, –, –. Il n'y a pas d'arête entre et . Ce graphe sert dans tout le cours.
Sommets adjacents, ordre, degré
- Deux sommets sont adjacents (on dit aussi voisins) lorsqu'une arête les relie.
- L'ordre d'un graphe est son nombre de sommets.
- Le degré d'un sommet est le nombre d'arêtes dont il est une extrémité, c'est-à-dire le nombre de ses voisins.
Exemple résolu
Dans , et sont adjacents, et non. est d'ordre 4 (il a 4 sommets et 5 arêtes). Degrés (nombre de voisins) : : 2 (, ) ; : 3 (, , ) ; : 3 (, , ) ; : 2 (, ).
Le graphe complet
Un graphe d'ordre est complet lorsque deux sommets distincts quelconques sont toujours adjacents. On le note souvent . Alors :
- chaque sommet est adjacent aux autres : tous les sommets sont de degré ;
- possède arêtes.
Pourquoi ? Chacun des sommets est l'extrémité de arêtes, soit extrémités. Chaque arête ayant deux extrémités, ce décompte compte chaque arête deux fois : on divise par 2.
Exemple résolu
Six équipes disputent un tournoi où chacune rencontre une fois chacune des autres. Équipes et matchs sont les sommets et les arêtes d'un graphe où deux sommets quelconques sont adjacents : c'est . Chaque équipe joue matchs et le tournoi en compte .
n'est pas complet : et ne sont pas adjacents. En ajoutant l'arête –, on obtient , qui a bien arêtes.
Chaînes et connexité
Chaîne et longueur
Une chaîne est une suite de sommets dans laquelle deux sommets consécutifs sont adjacents. Sa longueur est le nombre d'arêtes parcourues, c'est-à-dire le nombre de sommets de la suite moins 1. Une chaîne peut repasser par un sommet ou une arête déjà empruntés.
Exemple résolu
Dans :
- –– est une chaîne de longueur 2 : elle emprunte – puis – ;
- ––– est une chaîne de longueur 3 ;
- ––– est aussi une chaîne de longueur 3, qui repasse par ;
- –– n'est pas une chaîne, car et ne sont pas adjacents.
Graphe connexe
Un graphe est connexe lorsque deux sommets quelconques sont toujours reliés par au moins une chaîne : il est « d'un seul tenant ». Pour le prouver, il suffit de trouver un sommet relié par une chaîne à chacun des autres ; pour prouver le contraire, exhibe deux sommets qu'aucune chaîne ne relie.
Exemple résolu
est connexe : est adjacent à , et , donc deux sommets quelconques sont reliés par une chaîne passant par . Le graphe de sommets à et d'arêtes –, –, – n'est pas connexe : depuis , on n'atteint que et , donc aucune chaîne ne relie à .
Modéliser une situation par un graphe
Pour modéliser, réponds à deux questions : quels objets deviennent les sommets ? Quelle relation se traduit par une arête ? Traduis ensuite la question posée dans le vocabulaire des graphes.
Exemple résolu
Des lignes de bus directes relient cinq villes : et , et , et , et , et .
- Sommets : les villes ; arêtes : les lignes directes. Le graphe est d'ordre 5.
- « Combien de lignes desservent ? » se traduit par le degré de : 3.
- « Peut-on aller de toute ville à toute autre ? » se traduit par la connexité : oui, car est relié à , , par une arête et à par ––.
Graphe orienté
Quand la relation a un sens (rue à sens unique, « suit » sur un réseau social), on utilise un graphe orienté : chaque lien est un arc, d'un sommet de départ vers un sommet d'arrivée. Un chemin est une suite de sommets reliés par des arcs pris dans leur sens ; sa longueur est son nombre d'arcs.
La matrice d'adjacence
On numérote une fois pour toutes les sommets d'un graphe d'ordre , de à . La matrice d'adjacence du graphe est la matrice carrée d'ordre dont le coefficient , ligne et colonne , vaut si les sommets et sont adjacents (graphe orienté : s'il existe un arc de vers ), et sinon.
Pour un graphe non orienté :
- est symétrique () : une arête relie à comme à ;
- sa diagonale ne contient que des , aucune arête ne reliant un sommet à lui-même ;
- la somme des coefficients de la ligne est le degré du sommet .
Exemple résolu
Pour , dans l'ordre , , , , la ligne de porte un dans les colonnes de et de , un ailleurs ; on fait de même pour chaque sommet :
Contrôle : est symétrique et les sommes des lignes, , , , , redonnent les degrés.
Exemple orienté. Sur un réseau social, suit et , suit , suit ; un arc va de vers si suit . Dans l'ordre , , :
n'est pas symétrique : suit , mais ne suit pas .
Compter les chemins avec les puissances de la matrice
Théorème. Soit la matrice d'adjacence d'un graphe d'ordre , orienté ou non. Pour tout entier , le coefficient de situé ligne , colonne , est égal au nombre de chaînes (de chemins si le graphe est orienté) de longueur allant du sommet au sommet .
En particulier, il existe une chaîne de longueur de à si et seulement si ce coefficient n'est pas nul.
Exemple résolu
Pour , on calcule ligne par colonne. Ligne , colonne : la ligne de est , , , , la colonne de aussi, d'où . On procède ainsi pour chaque coefficient, puis :
- Ligne , colonne de : , les chaînes –– et ––.
- Ligne , colonne de : , les chaînes –––, –––, –––, ––– et –––.
- La diagonale de redonne les degrés , , , : une chaîne de longueur 2 de à est un aller-retour vers un voisin.
- Pour , le coefficient ligne , colonne de vaut : un seul chemin de longueur 2, .
Démonstration (à savoir refaire)
On raisonne par récurrence. Pour , on note : « pour tous sommets et , le coefficient est le nombre de chaînes de longueur de à ».
Initialisation. Une chaîne de longueur 1 de à est une arête entre et : il y en a une si et sont adjacents, aucune sinon. Ce nombre est , coefficient de : est vraie.
Hérédité. Soit tel que est vraie. Une chaîne de longueur de à se découpe selon son avant-dernier sommet : c'est une chaîne de longueur de à , suivie d'une arête entre et . Pour fixé, il y a débuts possibles, par hypothèse de récurrence, et arêtes finales possibles, soit chaînes. Deux chaînes d'avant-derniers sommets différents sont différentes, donc on additionne sur ; par définition du produit de deux matrices :
Donc est vraie.
Conclusion. est vraie pour tout entier . Pour un graphe orienté, la preuve est la même en remplaçant « arête » par « arc » et « chaîne » par « chemin ».
Les pièges
- Ordre ou nombre d'arêtes ? L'ordre compte les sommets : est d'ordre 4, avec 5 arêtes.
- Longueur d'une chaîne. Elle compte les arêtes, pas les sommets : –– est de longueur 2.
- Connexe ou complet ? Connexe demande une chaîne entre deux sommets quelconques, complet une arête : est connexe sans être complet.
- Sens des arcs. La ligne est le départ, la colonne l'arrivée : en les inversant, tu comptes les chemins de vers . Annonce toujours l'ordre des sommets.
- Puissance d'une matrice. est le produit , pas le carré de chaque coefficient, qui redonnerait .
- Longueur exacte. compte les chaînes de longueur exactement, pas « au plus ».
Ce qu'il faut retenir
- Ordre : nombre de sommets ; degré d'un sommet : nombre de ses voisins.
- : tous les sommets de degré et arêtes.
- Longueur d'une chaîne : nombre d'arêtes. Connexe : deux sommets quelconques sont reliés par une chaîne.
- si et sont adjacents (arc de vers si le graphe est orienté), sinon.
- Graphe non orienté : symétrique, diagonale nulle, somme de la ligne égale au degré de .
- Le coefficient ligne , colonne de est le nombre de chaînes (ou de chemins) de longueur de à .
- Ce résultat se démontre par récurrence, en découpant une chaîne de longueur selon son avant-dernier sommet.
À l'épreuve
Un exercice peut partir d'une situation concrète : réseau, plan, tournoi, relations entre personnes. Consignes possibles :
- « Modélise la situation par un graphe », puis donne son ordre et ses degrés.
- « Le graphe est-il connexe ? complet ? » : justifie par des chaînes, ou par deux sommets non reliés.
- « Écris la matrice d'adjacence », dans l'ordre des sommets imposé.
- « Combien de chemins de longueur 3 relient à ? » : se calcule à la main, une puissance plus grande peut être fournie. Cite le théorème, désigne le coefficient lu et conclus par une phrase.
- La démonstration par récurrence, en entier ou par étapes.
Les erreurs à éviter : une matrice sans ordre des sommets annoncé, un nombre lu dans sans citer le théorème, une longueur comptée en sommets.