Simulic
Français

Chaînes et cycles eulériens – les sept ponts de Königsberg

MathématiquesEnsembles, logique et graphes16–17 ans

Chargement…

Partager Signaler un problème

Dessinez ou modifiez un graphe (les sommets sont des terres, les arêtes des ponts) et voyez aussitôt le degré de chaque sommet, la somme des degrés égale au double du nombre d'arêtes et la conclusion tirée du nombre de sommets impairs : cycle eulérien, chaîne eulérienne ou ni l'un ni l'autre. Touchez vous-même les arêtes pour essayer de traverser chacune exactement une fois, ou laissez l'algorithme de Fleury (éviter les ponts) ou celui de Hierholzer (raccorder des cycles) trouver le parcours pas à pas.

Leçon : Chaînes et cycles eulériens

Ce qu’elle montre

En 1736, Leonhard Euler s'est demandé si une promenade dans Königsberg pouvait traverser chacun de ses sept ponts exactement une fois. En remplaçant les terres par des sommets et les ponts par des arêtes, il a montré que la réponse ne dépend que des degrés. Un graphe connexe possède un cycle eulérien quand tous les sommets sont de degré pair, et une chaîne eulérienne quand exactement deux sommets sont de degré impair ; la chaîne part alors de l'un et arrive à l'autre. La simulation autorise plusieurs arêtes entre deux mêmes sommets, mais pas de boucles, et la carte de Königsberg est simplifiée.

Mode d’emploi

Commencez par Les sept ponts de Königsberg et lisez les degrés et la conclusion. Passez le Mode sur Parcourir à la main et touchez les arêtes pour essayer de traverser chaque pont une fois. En mode Dessiner / déplacer, ajoutez ou reliez des sommets jusqu'à ce que la conclusion change, puis choisissez Fleury (éviter les ponts) ou Hierholzer (raccorder des cycles) et appuyez sur Pas à pas ou Lancer pour voir le parcours se construire.

Paramètres modifiables

  • Graphe de départ Les sept ponts de Königsberg, Enveloppe (sans lever le crayon), Deux triangles avec un sommet commun, Graphe complet à 5 sommets (K5), Page blanche – dessinez le vôtre
  • Algorithme Fleury (éviter les ponts), Hierholzer (raccorder des cycles)
  • Vitesse d'animation 0,5–4 arêtes/s

Questions à explorer

  1. Pourquoi est-il impossible de traverser chacun des sept ponts de Königsberg exactement une fois ?
  2. Combien de ponts faut-il ajouter au minimum pour obtenir une chaîne eulérienne, et où ?
  3. Pourquoi une chaîne eulérienne doit-elle partir d'un sommet impair et arriver à l'autre ?

Simulations associées