Sciences · Mathématiques
La théorie des graphes
Un graphe est un ensemble de points, les sommets, reliés par des lignes, les arêtes. La théorie des graphes étudie ces réseaux : chemins, connexions, coloriages et plus courts trajets.
Mis à jour le 4 min de lecture
Un réseau routier, le métro, Internet, un réseau social, un arbre généalogique, les liaisons entre atomes d’une molécule : tous peuvent être représentés par des points reliés par des traits. La théorie des graphes fournit le langage et les méthodes pour raisonner sur ces structures. Née d’une énigme de promenade au XVIIIe siècle, elle est devenue l’un des piliers de l’informatique et de la recherche opérationnelle.
Le vocabulaire essentiel
| Terme | Définition | Exemple |
|---|---|---|
| Degré d’un sommet | Nombre d’arêtes qui en partent | Nombre d’amis d’une personne |
| Sommets adjacents | Reliés par une arête | Deux stations voisines |
| Chaîne (chemin) | Suite de sommets reliés de proche en proche | Un itinéraire |
| Cycle | Chaîne fermée qui revient à son point de départ | Une tournée |
| Graphe connexe | Il existe une chaîne entre deux sommets quelconques | Réseau sans île isolée |
| Graphe complet | Chaque sommet est relié à tous les autres | Tournoi où chacun affronte chacun |
| Arbre | Graphe connexe sans cycle | Arbre généalogique, organigramme |
| Distance | Nombre d’arêtes de la plus courte chaîne (ou somme des poids) | Nombre de correspondances |
Le lemme des poignées de main
Dans tout graphe, la somme des degrés est égale au double du nombre d’arêtes : chaque arête est comptée deux fois, une fois par extrémité.
somme des degrés = 2 × nombre d'arêtes
Conséquence : le nombre de sommets de degré impair est toujours pair.
Les ponts de Königsberg et les chemins eulériens
La ville de Königsberg (aujourd’hui Kaliningrad) était traversée par une rivière formant deux îles, reliées aux rives par sept ponts. Peut-on faire une promenade qui traverse chaque pont une seule fois ? En 1736, Leonhard Euler démontre que non, en remplaçant chaque terre par un point et chaque pont par une arête.
Théorème d’Euler : un graphe connexe possède
- un cycle eulérien (passant une fois par chaque arête et revenant au départ) si et seulement si tous ses sommets sont de degré pair ;
- une chaîne eulérienne (sans retour au départ) si et seulement si il a exactement 0 ou 2 sommets de degré impair ; elle part alors de l’un et arrive à l’autre.
À Königsberg, les quatre terres avaient des degrés 5, 3, 3 et 3 : quatre sommets impairs, promenade impossible. C’est le principe des jeux « dessiner une figure sans lever le crayon ni repasser sur un trait ».
Les chemins hamiltoniens
Un chemin hamiltonien passe une fois par chaque sommet (et non chaque arête). Contrairement au cas eulérien, il n’existe aucun critère simple pour savoir s’il en existe un. Le célèbre problème du voyageur de commerce (trouver la tournée la plus courte passant par toutes les villes) en découle ; c’est un problème réputé difficile pour les ordinateurs dès que le nombre de villes grandit.
Le plus court chemin
Dans un graphe pondéré, l'algorithme de Dijkstra (1959) trouve le plus court chemin d’un sommet à tous les autres. C’est le principe des GPS et des calculateurs d’itinéraires, qui travaillent sur des graphes de millions de sommets (les carrefours) et d’arêtes (les tronçons). Voir les algorithmes.
La coloration de graphes
Colorier un graphe, c’est attribuer une couleur à chaque sommet de sorte que deux sommets adjacents aient des couleurs différentes. Le plus petit nombre de couleurs nécessaire est le nombre chromatique. Applications : emplois du temps (deux cours ayant des élèves communs ne peuvent pas avoir lieu en même temps), attribution de fréquences radio, planification d’examens. Le résultat le plus célèbre est le théorème des quatre couleurs pour les cartes.
Les graphes planaires
Un graphe est planaire s’il peut être dessiné dans le plan sans que deux arêtes se croisent. Pour un graphe planaire connexe, la relation d’Euler s’applique : S − A + F = 2, où F compte les régions délimitées (y compris la région extérieure). L’énigme des trois maisons et trois puits (relier chacune de trois maisons à l’eau, au gaz et à l’électricité sans croisement) est impossible sur une feuille : le graphe correspondant n’est pas planaire.
Applications
| Domaine | Sommets | Arêtes |
|---|---|---|
| Transports | Gares, carrefours | Lignes, routes |
| Web | Pages | Liens hypertextes (classement des moteurs de recherche) |
| Réseaux sociaux | Personnes | Relations d’amitié ou d’abonnement |
| Chimie | Atomes | Liaisons |
| Biologie | Espèces | Relations proie-prédateur (voir la chaîne alimentaire) |
| Intelligence artificielle | Concepts | Relations (voir les graphes de connaissances) |
Le phénomène du « petit monde » observé dans les réseaux sociaux (environ six intermédiaires séparent deux personnes quelconques, selon les expériences de Stanley Milgram en 1967) est une propriété de distance dans un graphe.
Questions fréquentes
Qu’est-ce qu’un graphe en mathématiques ?
Un ensemble de sommets reliés par des arêtes. À ne pas confondre avec le graphique (ou courbe) d’une fonction.
Comment savoir si on peut tracer une figure sans lever le crayon ?
Compter les points d’où partent un nombre impair de traits. S’il y en a 0, c’est possible en revenant au départ ; s’il y en a 2, c’est possible en partant de l’un d’eux ; au-delà, c’est impossible.
Qu’est-ce qu’un arbre en théorie des graphes ?
Un graphe connexe sans cycle. Un arbre à n sommets possède toujours exactement n − 1 arêtes.
Pourquoi le problème des ponts de Königsberg est-il impossible ?
Parce que les quatre zones de terre sont reliées chacune par un nombre impair de ponts. Or une promenade empruntant chaque pont une fois exige au plus deux zones de degré impair.