Chaînes et cycles eulériens expliqués
Certaines figures se dessinent d'un seul trait, sans lever le crayon ni repasser sur une ligne, et d'autres non, aussi longtemps qu'on essaie. Inutile d'essayer : comptez les lignes en chaque coin. Si au plus deux coins ont un nombre impair de lignes, la figure peut être dessinée, et c'est en ces coins que le trait doit commencer et finir. Leonhard Euler a trouvé cette règle en 1736, et avec elle il a fondé la théorie des graphes.
Les sept ponts de Königsberg
La ville prussienne de Königsberg, aujourd'hui Kaliningrad, s'étendait sur les deux rives de la Pregel et sur deux îles, le Kneiphof et la Lomse. Sept ponts reliaient les quatre parties : deux du Kneiphof à chaque rive, un entre les deux îles, et un de la Lomse à chaque rive. Les habitants se demandaient si une promenade pouvait franchir chaque pont exactement une fois. Euler a répondu dans un mémoire présenté à l'Académie de Saint-Pétersbourg en 1735 et imprimé en 1741 : c'est impossible. Son idée clé fut de tout écarter sauf les parties de la ville et les ponts entre elles, ce que fait un graphe : un sommet par terre et une arête par pont, avec deux arêtes là où deux ponts relient les mêmes parties.
La règle des degrés
Le degré d'un sommet est le nombre d'arêtes qui y aboutissent. Un trait qui traverse un sommet entre par une arête et sort par une autre : il utilise les arêtes de ce sommet par paires. Seuls le premier et le dernier sommet du trait peuvent garder une arête sans partenaire. Un sommet de degré impair doit donc être le début ou la fin du trait. Le Kneiphof avait cinq ponts et les trois autres parties trois chacune : quatre sommets impairs, deux de trop. En général, un graphe connexe a un cycle eulérien, un trait qui finit où il a commencé, quand tous les degrés sont pairs, et une chaîne eulérienne quand exactement deux degrés sont impairs, de l'un à l'autre. Le nombre de sommets impairs n'est jamais un, ni aucun autre nombre impair : chaque arête ajoute 2 à la somme des degrés, qui est donc paire. Euler l'avait aussi remarqué, et on parle aujourd'hui du lemme des poignées de main.
Pourquoi la règle suffit
Euler a montré qu'une figure qui a plus de deux sommets impairs ne peut pas être tracée, et a affirmé sans preuve que toute autre figure connexe peut l'être. La preuve est venue de Carl Hierholzer, mathématicien allemand mort jeune en 1871 ; son article a paru en 1873. Partez d'un sommet impair s'il y en a un, sinon de n'importe où, et suivez des arêtes inutilisées tant que vous le pouvez. Comme tous les autres sommets sont de degré pair, on ne peut rester bloqué qu'au sommet d'arrivée. S'il reste des arêtes, certaines touchent le parcours déjà fait, puisque la figure est connexe. Depuis un tel sommet, marchez de nouveau jusqu'à être bloqué, ce qui arrive cette fois en revenant à ce sommet, et insérez la boucle dans le parcours à cet endroit. Répétez jusqu'à ce qu'il ne reste aucune arête. La preuve est aussi l'algorithme le plus rapide : chaque arête n'est examinée qu'un nombre fixe de fois.
L'algorithme de Fleury : ne coupez pas les ponts
Un trait peut échouer même sur une figure traçable. Prenez deux triangles reliés par une seule arête et partez d'un coin du premier : si vous passez au second triangle avant d'avoir fini le premier, vous ne reviendrez jamais. L'arête de liaison est un pont : la retirer sépare la figure en deux. L'algorithme de Fleury, de 1883, donne une règle : à chaque sommet, prenez une arête qui n'est pas un pont des arêtes restantes, sauf s'il n'y en a pas d'autre. En la suivant, on termine toujours. Tester un pont prend du temps, si bien que l'algorithme de Fleury est plus lent que celui de Hierholzer, mais c'est celui qu'on peut suivre au crayon, et l'indice de l'application s'en sert.
Réparer une figure
Une figure à k sommets impairs demande k/2 traits. Pour la tracer d'un seul, ajoutez des arêtes qui relient les sommets impairs deux à deux : chaque nouvelle arête rend pairs deux sommets impairs. Avec k/2 − 1 arêtes, il reste deux sommets impairs et l'on obtient une chaîne ; avec k/2, il n'en reste aucun et l'on obtient un cycle. Un pont de plus à Königsberg, entre deux quelconques des quatre parties, aurait rendu la promenade possible, et deux auraient permis un tour complet. L'histoire a fait quelque chose de semblable : deux ponts ont disparu pendant la Seconde Guerre mondiale et deux ont été remplacés par une route moderne, et les cinq ponts qui se trouvent aujourd'hui aux anciens emplacements peuvent être franchis une fois chacun, d'une île à l'autre.
Compter les façons
La maison de saint Nicolas, un carré avec ses deux diagonales et un toit, est la version enfantine allemande de l'énigme : « Das ist das Haus vom Ni-ko-laus » compte huit syllabes, une par ligne. Ses deux coins du bas sont les seuls sommets impairs, et il y a exactement 44 façons de la dessiner depuis chacun, 88 en tout. Pour les graphes orientés, le nombre de cycles eulériens est donné par une formule, le théorème BEST, du nom de de Bruijn, van Aardenne-Ehrenfest, Smith et Tutte. Pour les graphes ordinaires, on ne connaît pas de telle formule, et le comptage passe pour difficile en général : l'application compte donc les petites figures en essayant toutes les façons, en écartant les pas qui couperaient la figure en deux.
Où servent les chaînes eulériennes
Un chasse-neige, une balayeuse ou un facteur veut parcourir chaque rue une fois et revenir. Si chaque carrefour a un nombre pair de rues, un cycle eulérien convient ; sinon, certaines rues doivent être parcourues deux fois, et choisir les moins coûteuses est le problème du postier chinois, posé par Meigu Guan en 1962. Un traceur à plume ou une découpeuse laser gagne du temps en traçant le plus de lignes possible sans lever l'outil. En séquençage du génome, des millions de courts fragments d'ADN sont assemblés en cherchant une chaîne eulérienne dans un graphe de de Bruijn, où chaque fragment est une arête. Et la même règle dit quels dessins d'un cahier de jeux valent la peine d'être essayés.
À vous d'explorer
Ouvrez le chercheur de chaînes eulériennes pour tracer vous-même douze figures, de Königsberg en 1736 et aujourd'hui aux étoiles, aux carrés emboîtés et à un cube, ou dessinez les vôtres avec des arêtes parallèles. Les sommets impairs sont remplis, chaque sommet affiche son degré, et la règle des degrés sous la figure dit ce qui est possible et quelles arêtes répareraient la figure. Si vous restez bloqué, l'application dit si vous êtes parti du mauvais sommet ou si vous avez franchi un pont trop tôt, et à quel pas. Indice donne une arête sûre, et Résoudre dessine la figure avec l'algorithme de Fleury, en montrant le test du pont, ou avec celui de Hierholzer, en montrant chaque insertion.
Questions fréquemment posées
Une chaîne eulérienne est-elle la même chose qu'une chaîne hamiltonienne ?
Non. Une chaîne eulérienne utilise chaque arête une fois et peut passer plusieurs fois par un sommet ; une chaîne hamiltonienne passe une fois par chaque sommet et n'utilise pas forcément toutes les arêtes. Compter les sommets impairs dit tout de suite si un graphe a une chaîne eulérienne, mais on ne connaît aucun test rapide pour les chaînes hamiltoniennes, et en trouver une est l'un des problèmes difficiles classiques de l'informatique.
La règle des degrés vaut-elle quand deux sommets sont reliés par plusieurs arêtes ?
Oui. Chaque arête compte dans le degré de ses deux extrémités, qu'une autre arête relie ou non les deux mêmes sommets. Königsberg est un tel multigraphe, avec deux ponts du Kneiphof à chaque rive. Une arête qui relie un sommet à lui-même, une boucle, ajoute 2 à son degré et ne change jamais sa parité.
Et avec des rues à sens unique ?
Dans un graphe orienté, chaque arête a un sens, et la règle compare les arêtes qui entrent dans chaque sommet et celles qui en sortent. Il y a un cycle eulérien quand chaque sommet a autant d'arêtes entrantes que sortantes et que les arêtes tiennent ensemble, et une chaîne eulérienne quand un sommet a une arête sortante de plus, un autre une arête entrante de plus, et que tous les autres sont équilibrés. La chaîne va alors du premier au second.
Une figure peut-elle avoir exactement un sommet impair ?
Non. La somme des degrés de tous les sommets vaut deux fois le nombre d'arêtes, car chaque arête a deux extrémités. Cette somme est paire, donc le nombre de degrés impairs qu'elle contient l'est aussi : 0, 2, 4 et ainsi de suite, jamais 1 ni 3.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir le chercheur de chaînes eulériennes