Graphes, degrés et parcours eulériens
Définition et périmètre FAIT
Un multigraphe fini non orienté G=(V,E) comprend un ensemble fini de sommets V et une collection finie d'arêtes E. Chaque arête relie deux sommets sans imposer de sens de parcours. Plusieurs arêtes peuvent relier la même paire de sommets ; une boucle peut aussi relier un sommet à lui-même. Un graphe simple est le cas particulier sans boucle ni arêtes parallèles.
Ce cadre est choisi parce que plusieurs ponts de Königsberg reliaient les mêmes zones terrestres : les représenter exige des arêtes parallèles. L'article ne traite ni les graphes orientés, où une arête possède un sens, ni les graphes pondérés, où elle porte par exemple une distance ou un coût.
Le multigraphe sous-jacent ne conserve donc que la relation d'incidence : quels sommets chaque arête relie. Les positions dessinées, les longueurs et les angles ne font pas partie de sa définition. On peut ajouter ces données au modèle lorsqu'elles sont utiles, mais elles ne sont pas nécessaires au problème étudié ici.
Le vocabulaire minimal FAIT
| Terme | Définition dans un multigraphe non orienté |
|---|---|
| Degré d'un sommet | Nombre d'extrémités d'arêtes incidentes au sommet ; une boucle compte pour 2 |
| Marche | Suite de sommets et d'arêtes incidentes ; sommets et arêtes peuvent se répéter |
| Piste | Marche qui ne répète aucune arête |
| Chemin | Marche qui ne répète aucun sommet |
| Circuit | Piste fermée : le départ et l'arrivée coïncident |
| Cycle | Circuit qui ne répète aucun sommet, sauf le sommet commun de départ et d'arrivée |
| Connexe | Un chemin relie toute paire de sommets |
Une piste eulérienne utilise chaque arête exactement une fois. Elle est ouverte si ses extrémités diffèrent et devient un circuit eulérien si elle revient à son sommet de départ. Le mot « eulérien » porte ici sur les arêtes, pas sur les sommets.
Le lemme des poignées de main FAIT
Chaque arête ordinaire possède deux extrémités et ajoute 1 au degré de chacun de ses sommets. Une boucle possède elle aussi deux extrémités, toutes deux sur le même sommet, et ajoute donc 2 à son degré. En comptant avec multiplicité, chaque arête contribue exactement 2 à la somme totale :
v∈V∑deg(v)=2∣E∣
Le membre de droite est pair. Les sommets de degré pair apportent une somme paire ; la somme des degrés impairs doit donc être paire elle aussi. Or une somme d'entiers impairs est paire si et seulement si elle contient un nombre pair de termes. Il y a donc toujours un nombre pair de sommets de degré impair.
Dans un graphe simple représentant une assemblée, une arête signifie que deux personnes se sont serré la main. Le lemme affirme alors que le nombre de personnes ayant serré un nombre impair de mains est pair. Cette image explique son nom, mais la preuve vaut aussi pour les multigraphes et les boucles avec la convention de degré précédente.
Les ponts de Königsberg FAIT
Le problème historique décrit quatre zones terrestres reliées par sept ponts. La question était de trouver une promenade franchissant chaque pont exactement une fois, sans exiger de revenir au départ.
Euler désigna les zones par des lettres et représenta les traversées successives par des suites de lettres. Dans la reformulation graph-théorique moderne, chaque zone devient un sommet et chaque pont une arête. Le multigraphe obtenu possède quatre sommets de degrés 5, 3, 3 et 3. Leur somme vaut 14, soit deux fois les sept arêtes, conformément au lemme.
Dans une piste eulérienne, toutes les arêtes incidentes sont utilisées. Chaque passage par un sommet intermédiaire les consomme par paires : une pour entrer, une pour sortir. Seuls le départ et l'arrivée d'une piste eulérienne ouverte ont donc un degré impair, tandis qu'un circuit eulérien n'en possède aucun.
Königsberg en possède quatre. Aucune piste utilisant chacun des sept ponts exactement une fois n'existe. Euler établit cette impossibilité et formula les règles générales de parité ; le théorème moderne donne la caractérisation complète.
Le théorème eulérien moderne FAIT
Considérons un multigraphe fini non orienté dans lequel tous les sommets de degré non nul appartiennent à une même composante connexe.
- Il admet un circuit eulérien si et seulement si tous ses sommets ont un degré pair.
- Il admet une piste eulérienne ouverte si et seulement si exactement deux sommets ont un degré impair ; ils en sont nécessairement le départ et l'arrivée.
La nécessité vient de l'appariement entrée–sortie. La suffisance est constructive. Lorsque tous les degrés sont pairs, on part d'un sommet incident à une arête et l'on suit des arêtes encore inutilisées. On ne peut rester bloqué sur un autre sommet : chaque arrivée y laisse, par parité, une arête inutilisée pour repartir. La piste finit donc par revenir au départ et forme un circuit.
S'il reste des arêtes, la connexité garantit qu'un sommet du circuit touche une partie encore inutilisée. On construit depuis ce sommet un nouveau circuit, puis on l'insère dans le premier. En répétant l'opération, on obtient un circuit contenant toutes les arêtes : c'est le principe de l'algorithme de Hierholzer.
S'il existe exactement deux sommets impairs, on ajoute temporairement une arête entre eux. Tous les degrés deviennent pairs ; on construit un circuit eulérien, puis on retire l'arête ajoutée. Le circuit s'ouvre alors en une piste dont les extrémités sont précisément les deux sommets impairs.
Modéliser exige de choisir la bonne structure FAIT
Routes, dépendances logicielles, molécules et circuits électriques peuvent tous être représentés par des graphes, mais pas par le même modèle sans qualification.
- Un réseau routier peut être non orienté ou orienté et porte souvent des distances ou des temps de trajet.
- Un graphe de dépendances est généralement orienté : un cycle y exprime une dépendance circulaire.
- Un graphe moléculaire porte des étiquettes sur les atomes et les liaisons.
- Un réseau électrique ajoute des grandeurs physiques et des lois qui ne sont pas contenues dans la seule incidence.
Le gain de l'abstraction n'est donc pas qu'un algorithme unique conviendrait partout. Il est de séparer la structure commune — sommets et arêtes — des informations propres au domaine, puis de choisir un théorème ou un algorithme dont les hypothèses correspondent exactement au graphe construit.
Résumé
Dans un multigraphe fini non orienté dont les arêtes appartiennent à une même composante, la parité des degrés décide si chaque arête peut être parcourue exactement une fois : zéro sommet impair pour un circuit, exactement deux pour une piste ouverte.