Parcours et graphes Eulériens

Une chaîne Eulérienne est une chaîne qui passe une fois et une seule par chaque arête d'un graphe.
Un cycle Eulérien passe une fois et une seule par chaque arête d'un graphe et revient au point de départ. Un graphe est dit Eulérien s'il comporte une chaîne Eulérienne.
On peut aussi s'intéresser au cas orienté et définir de même des chemins et circuits Eulériens.
Cette appelation vient d'un problème posé par Euler en 1766.

La ville de Koenigsberg est traversée par la rivière Pregel qui possède deux iles, reliées par 7 ponts. Un piéton peut-il passer une fois et une seule sur chaque pont au cours de sa promenade ?
La réponse est non, comme le montre le théorème suivant.

Théorème d'Euler

Un multigraphe connexe admet une chaîne Eulérienne si et seulement si le nombre de sommets impairs est 0 ou 2. Il admet un cycle Eulérien si et seulement si il n'a que des sommets pairs.

Démonstration

La condition est nécessaire puisque pour chaque sommet sauf le départ et l'arrivée, chaque fois que l'on arrive à ce sommet par un arc, on en repart par un autre.

Démontrons alors que si un graphe a deux points impairs A et B, il existe une chaîne Eulérienne reliant ces deux points. Supposons que ce soit vrai pour tous les graphes de moins de N sommets et examinons un graphe G de N sommets.
Partant de A, chaque fois que l'on arrive à un sommet, on peut en repartir sauf si on arrive en B par le dernier chemin disponible. Si toutes les arêtes ont été visitées on a trouvé une chaîne Eulérienne. Sinon la partie du graphe non visitée a au moins un sommet de moins (B) et a tous ses sommets pairs pour chacune de ses composantes connexes et chacune comporte donc un cycle Eulérien. En fusionnant le parcours visité avec tous ces cycles, on obtient une chaîne Eulériennne entre A et B.

Les ponts de Koenigsberg

Le graphe possède uniquement des sommets de degré 3 (chaque rive et la petite ile) et 5 (la grande ile) soit 4 sommets impairs. Le parcours du promeneur est donc impossible.

Application - les parcours d'un seul trait

On peut ainsi chercher à tracer une figure d'un seul trait sans lever le crayon.
Dans le problème classique de l'enveloppe, le théorème d'Euler nous donne alors immédiatement les points de départ et d'arrivée obligatoires.

Et de même dans des cas plus compliqués :

 

Dans les cas d'imposibilité ceci permet de déterminer comment modifier l'énoncé pour qu'il devienne possible. Par exemple ici le graphe peut être parcouru en 2 fois.
De façon générale si un graphe possède 2n sommets impairs, il peut être parcouru en n traits.