Problème des ponts de Koenigsberg

Le problème des ponts de Koenigsberg est considéré comme l'origine de la théorie des graphes. Résolu par Euler, c'est une bonne porte d'entrée vers la modélisation d'un problème en terme de graphes.

Le poster Euler et les graphes est disponible pour prêt à l'IREM.

La maquette des ponts de Koenigsberg permet de manipuler le concept de graphe eulérien. En ajoutant un pont, on peut ensuite rechercher une promenade permettant de parcourir tous les ponts sans retour au point de départ. Le parallèle avec le jeu de domino permet de trouver facilement de telles promenades et met facilement en relation leur existence avec la parité du degré des sommets du graphe.