Ponts de Königsberg et cycle eulérien
La ville de Königsberg est traversée par la rivière Pregolya, et comporte deux iles. Ces iles sont reliées entre elles et aux berges par des ponts, comme sur la figure ci-dessous. Est-il possible de passer d'une berge à l'autre de la ville en passant, une et une seule fois, par tous les ponts que la ville comporte? Est-il possible de passer une et une seule fois par chaque pont, et de revenir à son point de départ?
Modélisation par la théorie des graphes
Définition : On appelle degré d'un sommet d'un graphe (non orienté) le nombre d'arêtes partant de ce sommet.
Définition :
Théorème :
- une chaine eulérienne est une chaine passant une et une seule fois par toutes les arêtes du graphe.
- un cycle eulérien est une chaine eulérienne dont le sommet de départ et le sommet d'arrivée sont identiques.
- Un graphe connexe possède une chaine eulérienne si et seulement si ses sommets sont tous de degré pair sauf au plus deux.
- Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Le problème des ponts de Königsberg peut se modéliser à l'aide d'un graphe de la façon suivante :


Consulter aussi...