Les graphes

Un graphe modélise des objets et les relations entre eux. Les objets deviennent des sommets ; les relations deviennent des arêtes dans un graphe non orienté. Pour un réseau de villes, un sommet peut représenter une ville et une arête une liaison directe. Pour un groupe de personnes, une arête peut représenter une relation réciproque. Le choix des sommets et des arêtes fait partie du raisonnement : un dessin sans définition ne constitue pas encore un modèle.

L’ordre d’un graphe est le nombre de ses sommets. Deux sommets sont adjacents lorsqu’une arête les relie directement. Dans un graphe simple non orienté, il n’y a ni boucle reliant un sommet à lui-même, ni plusieurs arêtes entre les mêmes sommets. Sauf indication contraire, les graphes non orientés de cette leçon sont simples. Un graphe complet d’ordre n relie chaque paire de sommets distincts ; il comporte n(n − 1)/2 arêtes.

La position des sommets sur la feuille n’a pas de signification mathématique si aucune coordonnée n’est imposée. Allonger une arête ou déplacer un sommet ne change pas le graphe. Deux traits qui se croisent ne créent pas un sommet supplémentaire : seul un sommet explicitement indiqué compte. De même, une arête ne mesure pas une distance ; pour représenter un coût ou une longueur, il faut ajouter un poids.

Le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes, c’est-à-dire qui arrivent à ce sommet. Pour un graphe simple d’ordre n, il est compris entre 0 et n − 1. Un sommet de degré zéro est isolé. Dans un graphe complet d’ordre n, chaque sommet a pour degré n − 1. Le degré ne donne pas le nombre de sommets que l’on peut atteindre en plusieurs étapes : il décrit seulement les voisins directs.

La somme des degrés d’un graphe non orienté vaut deux fois son nombre d’arêtes. Chaque arête possède deux extrémités et ajoute donc une unité au degré de chacune. Ce double comptage démontre la formule sans supposer une forme particulière du dessin. Il entraîne que le nombre de sommets de degré impair est pair : la somme des degrés pairs est paire, donc la somme des degrés impairs doit l’être aussi.

Dans un graphe non orienté, une chaîne est une succession de sommets telle que deux sommets consécutifs soient adjacents. Sa longueur est le nombre d’arêtes parcourues, donc une unité de moins que le nombre de sommets écrits dans la succession. On peut repasser par un sommet ou une arête si aucune contrainte ne l’interdit. Une chaîne fermée revient au sommet de départ. Une chaîne sans répétition de sommets décrit un trajet plus contraint.

Un graphe est connexe lorsque toute paire de sommets peut être reliée par une chaîne. Il ne suffit pas que chaque sommet possède un voisin. Deux triangles disjoints fournissent un contre-exemple : chaque sommet a deux voisins, mais aucun sommet du premier triangle ne peut rejoindre le second. Une composante connexe est un groupe maximal de sommets reliés entre eux par des chaînes.

Pour tester la connexité, on part d’un sommet et on marque ses voisins, puis les voisins des sommets marqués, jusqu’à ne plus rien ajouter. Si tous les sommets ont été marqués, le graphe est connexe. Cette exploration termine sur un graphe fini : à chaque étape utile, au moins un sommet nouveau est ajouté. Elle évite de conclure à partir de l’aspect visuel, qui peut devenir trompeur lorsque les arêtes se croisent.

Lorsque les relations ne sont pas réciproques, on utilise un graphe orienté. Un arc va d’un sommet de départ vers un sommet d’arrivée. Une route à sens unique ou un lien d’une page vers une autre ne doit pas être modélisé par une arête réciproque. Dans cette leçon, on appelle chemin une succession respectant le sens des arcs. Les mots chaîne et chemin peuvent varier selon les ouvrages ; il faut toujours préciser orientation, longueur et répétitions autorisées.

Un graphe pondéré associe un nombre à chaque arête ou arc. Le poids peut être une durée, une distance, un coût ou une probabilité selon le problème. La longueur d’un chemin compte les arcs ; son coût additionne leurs poids lorsque le modèle le prévoit. Un trajet comportant moins d’arcs peut avoir un coût supérieur. Le modèle doit indiquer quelle grandeur on souhaite minimiser ou calculer.

Un graphe simplifie une situation ; il faut donc examiner ce qu’il oublie. Une route peut être fermée, un coût peut dépendre de l’heure et une relation peut changer. Ces informations n’apparaissent pas dans un graphe fixe si on ne les ajoute pas. Une conclusion correcte sur le graphe reste conditionnée par les hypothèses de modélisation. Cette réserve ne rend pas l’outil moins utile ; elle précise le sens du résultat.

Erreurs fréquentes : prendre un croisement de traits pour un sommet ; oublier une diagonale ; compter les sommets au lieu des arêtes ; affirmer la connexité à partir des seuls degrés. Une liste des arêtes constitue souvent une seconde représentation utile pour contrôler le dessin. Le prochain chapitre sur les matrices introduira une autre représentation, adaptée au calcul et à l’étude de suites.

Pour t’entraîner, ouvre S’entraîner dans /exercices. Tu peux aussi transformer un petit réseau réel en graphe, puis expliquer à quelqu’un ce que ton dessin permet de calculer. Demande-lui quelles informations manquent : cette discussion aide à distinguer un modèle utile d’un dessin seulement ressemblant.