Théorie > Combinatoire > Théorie des graphes
Graphes eulériens
Problème des sept ponts de Königsberg
Le problème suivant est très connu en mathématiques, et est réputé pour être à l'origine de la théorie des graphes.Problème des sept ponts de Königsberg
La ville de Königsberg est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessous. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg passant une et une seule fois par chaque pont de la ville.
On peut facilement réécrire ce problème en termes de graphes, en prenant les quatre parcelles de terre pour sommets et les sept ponts pout arêtes. Le problème revient alors à déterminer s'il existe un chemin passant une et une seule fois par chaque arête dans le graphe suivant :
Comme souvent pour de tels problèmes, on se persuade vite que le problème est impossible par essais et erreurs, mais le tout est de le prouver. C'est Euler qui y est parvenu, avec l'idée suivante : si un tel chemin existait, alors pour chaque sommet différent de celui de départ et de celui d'arrivée, il serait possible de repartir du sommet à chaque fois que l'on y arrive. Autrement dit, le nombre d'arêtes partant d'un tel sommet doit toujours être pair. Pour cette raison, on introduit la notion de degré d'un sommet désignant le nombre d'arêtes partant de ce sommet, et l'impossibilité d'effectuer une promenade complète dans les rue de Königsberg vient alors du fait que les degrés des $4$ sommets du graphe sont impairs, alors qu'il en faudrait au moins deux de degré pair.
Chemin et cycle eulérien
Réexprimons ce problème pour un graphe quelconque. On parle de chemin eulérien dans un graphe pour désigner un chemin passant une et une seule fois par chaque arête. De la même façon, on définit un cycle eulérien comme étant un cycle passant exactement une fois par chaque arête (cela revient à demander que la promenade se termine là où elle a commencé). Le problème des ponts de Königsberg revient à déterminer s'il existe un chemin eulérien dans un graphe donné. En fait, Euler est parvenu à donner une condition nécessaire et suffisante sur le graphe pour qu'un chemin eulérien existe.Théorème (existence d'un chemin eulérien)
Soit $G$ un graphe non-orienté n'ayant aucun sommet isolé (c'est-à-dire de degré nul). Il existe un chemin eulérien dans $G$ si et seulement si $G$ est connexe et possède exactement zéro ou deux sommets de degré impair.
Démonstration
Commençons par le sens $\Rightarrow$. On suppose qu'il existe un chemin eulérien dans un certain graphe $G$. Tout d'abord, $G$ est clairement connexe puisque le chemin passe par toutes les arêtes et donc tous les sommets de $G$. Pour la condition sur les degrés, notons $v$ le sommet de départ et $w$ le sommet d'arrivée du chemin. Puisque le chemin passe par toutes les arêtes, on peut facilement compter les degrés de chaque sommet en suivant le chemin. En effet, on peut initialement mettre tous les degrés à $0$ et, à chaque fois que l'on passe par un sommet en suivant notre chemin, on augmente son degré de $2$ puisqu'il y a une arête arrivant en ce sommet et une arête en repartant. Cela ne sera juste pas pareil au départ du chemin et à l'arrivée : on incrémente le degré de $v$ uniquement de $1$ au départ et celui de $w$ de $1$ également à l'arrivée. Ainsi, si $v \neq w$, alors ce sont les deux seuls ayant un degré impair, alors que si $v = w$, tous les sommets sont de degré pair.
Le sens $\Leftarrow$ est un peu plus compliqué. On suppose en fait être en présence d'un graphe $G$ connexe et vérifiant la condition sur les degrés et on va donner une façon de construire un chemin eulérien dans $G$. Nous illustrerons cette démonstration sur le graphe suivant.
S'il existe exactement deux sommets de degré impair, alors on les note $v$ et $w$. Si par contre ils sont tous de degré pair, alors on prend $v = w$ quelconque. Sur notre exemple, on prend $v = 1$ et $w = 2$. Nous allons construire un chemin eulérien reliant $v$ à $w$. L'idée est en fait assez simple : on part de $v$ et on prend une arête quelconque partant de $v$, comme $[1,3]$ sur notre exemple. Au vu des degrés des différents sommets, il existe toujours au moins une arête non encore empruntée partant du sommet auquel on arrive, sauf éventuellement si on est en $w$. On prend donc une telle arête, comme $[3, 2]$ sur notre exemple, et on continue de la sorte jusqu'à ce qu'il ne soit plus possible d'avancer.
Au vu de nos remarques sur les degrés, le sommet final auquel on sera coincé sera toujours forcément $w$. On a donc jusqu'ici trouvé un chemin reliant $v$ à $w$. Il n'est cependant pas certain qu'il soit eulérien : on n'est peut-être pas passé par toutes les arêtes.
Cependant, si on "supprime" toutes les arêtes par lesquelles on est déjà passé, on remarque que le nouveau graphe obtenu n'a plus que des sommets de degré pair. On peut donc agrandir notre chemin en partant d'un sommet du chemin dont toutes les arêtes n'ont pas encore été empruntées (comme $3$ sur notre exemple), et en effectuant le même procédé que précédemment avec les arêtes restantes jusqu'à revenir au même sommet.
On prolonge alors notre chemin initial en lui incluant la boucle que nous venons de créer. Sur notre exemple, on peut ainsi obtenir le chemin
$$[1, 3, 4, 6, 5, 3, 2, 1, 5, 4, 2].$$ Si le chemin obtenu n'est toujours pas eulérien, alors on peut bien sûr continuer à rajouter des boucles jusqu'à ce que ce soit le cas. Le fait que notre graphe soit connexe nous assure que l'on arrivera ainsi à un chemin eulérien.
Le sens $\Leftarrow$ est un peu plus compliqué. On suppose en fait être en présence d'un graphe $G$ connexe et vérifiant la condition sur les degrés et on va donner une façon de construire un chemin eulérien dans $G$. Nous illustrerons cette démonstration sur le graphe suivant.
S'il existe exactement deux sommets de degré impair, alors on les note $v$ et $w$. Si par contre ils sont tous de degré pair, alors on prend $v = w$ quelconque. Sur notre exemple, on prend $v = 1$ et $w = 2$. Nous allons construire un chemin eulérien reliant $v$ à $w$. L'idée est en fait assez simple : on part de $v$ et on prend une arête quelconque partant de $v$, comme $[1,3]$ sur notre exemple. Au vu des degrés des différents sommets, il existe toujours au moins une arête non encore empruntée partant du sommet auquel on arrive, sauf éventuellement si on est en $w$. On prend donc une telle arête, comme $[3, 2]$ sur notre exemple, et on continue de la sorte jusqu'à ce qu'il ne soit plus possible d'avancer.
Au vu de nos remarques sur les degrés, le sommet final auquel on sera coincé sera toujours forcément $w$. On a donc jusqu'ici trouvé un chemin reliant $v$ à $w$. Il n'est cependant pas certain qu'il soit eulérien : on n'est peut-être pas passé par toutes les arêtes.
Cependant, si on "supprime" toutes les arêtes par lesquelles on est déjà passé, on remarque que le nouveau graphe obtenu n'a plus que des sommets de degré pair. On peut donc agrandir notre chemin en partant d'un sommet du chemin dont toutes les arêtes n'ont pas encore été empruntées (comme $3$ sur notre exemple), et en effectuant le même procédé que précédemment avec les arêtes restantes jusqu'à revenir au même sommet.
On prolonge alors notre chemin initial en lui incluant la boucle que nous venons de créer. Sur notre exemple, on peut ainsi obtenir le chemin
$$[1, 3, 4, 6, 5, 3, 2, 1, 5, 4, 2].$$ Si le chemin obtenu n'est toujours pas eulérien, alors on peut bien sûr continuer à rajouter des boucles jusqu'à ce que ce soit le cas. Le fait que notre graphe soit connexe nous assure que l'on arrivera ainsi à un chemin eulérien.
On a donc une condition nécessaire et suffisante pour qu'il existe un chemin eulérien dans un graphe. Au vu de la démonstration donnée, on remarque que ce chemin est en fait un cycle si et seulement si il n'y a aucun sommet de degré impair.
Théorème (existence d'un cycle eulérien)
Soit $G$ un graphe non-orienté n'ayant aucun sommet isolé (c'est-à-dire de degré nul). Il existe un cycle eulérien dans $G$ si et seulement si $G$ est connexe et ne possède que des sommets de degré pair.
Losqu'il existe un cycle eulérien dans un graphe, on dit tout simplement qu'il s'agit d'un graphe eulérien.