- 0 sommet impair : un cycle, de n'importe quel sommet à lui-même
- 2 sommets impairs : une chaîne de l'un à l'autre
- 4 ou plus : impossible d'un seul trait
Chercheur de chaînes eulériennes
Peut-on dessiner la maison de saint Nicolas sans lever le crayon et sans repasser sur une ligne ? Oui, mais seulement en partant d'un des deux coins du bas, et il y a 44 façons depuis chacun. La raison tient au degré d'un sommet, le nombre de lignes qui s'y rejoignent : chaque fois que le crayon traverse un sommet, il utilise deux de ses lignes. Leonhard Euler a trouvé cette règle en 1736 avec les sept ponts de Königsberg. Tracez vous-même une figure, voyez où vous restez bloqué et pourquoi, demandez un indice ou regardez un algorithme la dessiner. Choisissez une figure et tracez-la : touchez un sommet pour commencer, puis les arêtes ou les sommets suivants dans l'ordre, ou faites glisser de sommet en sommet. Chaque arête ne sert qu'une fois. Retour annule un pas, Indice montre la prochaine arête sûre, et Résoudre déroule pas à pas l'algorithme de Fleury ou celui de Hierholzer. Les sommets impairs sont remplis, et la pastille de chaque sommet indique son degré. Sous Dessiner, touchez un endroit vide pour ajouter un sommet et deux sommets pour les relier, une fois de plus pour une deuxième arête ; faites glisser un sommet pour le déplacer. Effacer supprime sommets et arêtes. Quand plus de deux sommets sont impairs, Ajouter place les arêtes qui rendent la figure traçable.
Comment ça marche
- Choisissez une figure, comme les sept ponts de Königsberg, la maison de saint Nicolas ou une étoile, ou dessinez la vôtre sous Dessiner, avec autant d'arêtes que vous voulez entre deux sommets.
- Touchez un sommet pour commencer, puis les arêtes ou les sommets dans l'ordre, ou faites glisser de sommet en sommet. Si vous restez bloqué, la ligne d'état dit pourquoi ; Retour annule un pas et Indice montre une arête sûre.
- Lisez la règle des degrés sous la figure, ajoutez à une figure impossible les arêtes proposées, ou appuyez sur Résoudre pour voir l'algorithme de Fleury ou celui de Hierholzer la dessiner pas à pas.
Pourquoi les sommets impairs décident
Un trait qui traverse un sommet arrive par une ligne et repart par une autre : il utilise les lignes de ce sommet deux par deux. Une ligne ne peut rester sans partenaire que là où le trait commence ou finit. Un sommet qui a un nombre impair de lignes doit donc être le début ou la fin. Sans sommet impair, le trait finit là où il a commencé : c'est un cycle eulérien. Avec deux, il va de l'un à l'autre : c'est une chaîne eulérienne. Avec quatre ou plus, il y a trop d'extrémités pour un seul trait, et k sommets impairs demandent k/2 traits. Königsberg avait quatre terres, avec cinq, trois, trois et trois ponts : toutes impaires, donc aucune promenade ne pouvait franchir chaque pont une fois. Un pont de plus entre deux d'entre elles aurait rendu la promenade possible.
Les algorithmes de Fleury et de Hierholzer
Savoir qu'une figure peut être tracée ne suffit pas pour la tracer : un trait imprudent peut se couper des lignes dont il a encore besoin. L'algorithme de Fleury, de 1883, l'évite par une seule règle : ne jamais franchir un pont, c'est-à-dire une ligne dont la suppression séparerait les lignes restantes en deux morceaux, sauf s'il n'y a pas d'autre ligne. L'algorithme de Hierholzer, tiré d'un article paru en 1873, est plus rapide : marchez n'importe où jusqu'à être bloqué, ce qui ne peut arriver qu'au départ, puis, depuis un sommet du circuit qui a encore des lignes libres, parcourez une autre boucle fermée et insérez-la dans le circuit. Son temps de calcul est proportionnel au nombre d'arêtes, et c'est ainsi que les ordinateurs trouvent les chaînes eulériennes.
Questions fréquemment posées
Quelle est la différence entre une chaîne eulérienne et un cycle eulérien ?
Les deux utilisent chaque arête d'un graphe exactement une fois. Un cycle eulérien finit là où il a commencé ; une chaîne eulérienne finit ailleurs. Un graphe connexe a un cycle quand tous les sommets sont de degré pair, et une chaîne quand exactement deux sommets sont de degré impair ; la chaîne va alors de l'un à l'autre.
Pourquoi ne peut-on pas franchir une fois chacun des sept ponts de Königsberg ?
Représentez chaque terre par un sommet et chaque pont par une arête. L'île de Kneiphof avait cinq ponts et les trois autres terres trois chacune : les quatre sommets sont impairs. Une promenade ne peut commencer ou finir qu'à un sommet impair, et quatre, c'est trop. Un pont de plus entre deux d'entre eux laisse deux sommets impairs, et la promenade devient possible.
Combien y a-t-il de façons de dessiner la maison de saint Nicolas ?
44 depuis chacun des deux coins du bas, soit 88 en tout, en comptant un autre ordre ou un autre sens comme une autre façon. Depuis tout autre sommet, c'est impossible, car les coins du bas sont les deux seuls à avoir un nombre impair de lignes. L'application compte ainsi les façons pour les petites figures.
Qu'est-ce qu'un pont dans un graphe ?
Une arête dont la suppression sépare un graphe connexe en deux morceaux ; on dit aussi un isthme. L'algorithme de Fleury ne franchit jamais un pont des arêtes restantes tant qu'il a un autre choix, car une partie de la figure resterait derrière. Dans cette application, un trait bloqué après avoir franchi un pont trop tôt apprend de quel pas il s'agit.
Peut-il y avoir plus d'une arête entre deux sommets ?
Oui. Un graphe avec des arêtes parallèles s'appelle un multigraphe, et Königsberg en a besoin : deux ponts reliaient le Kneiphof à chaque rive. Sous Dessiner, touchez de nouveau deux sommets pour ajouter une arête entre eux, jusqu'à quatre. La règle des degrés s'applique de la même façon, en comptant chaque arête.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur