Problème des sept ponts de Königsberg

Le problème des sept ponts de Königsberg cherche à déterminer s'il existe un chemin permettant de revenir à son point de départ en empruntant une seule fois chaque pont de la ville. En 1735 Leonhard Euler démontre qu'un tel chemin eulérien n'existe pas pour la configuration de Königsberg. Ce problème est connu pour être à l'origine de la topologie et de la théorie des graphes. La ville de Königsberg (aujourd'hui Kaliningrad) est construite autour de deux îles situées sur le Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l'une ou l'autre des deux îles, comme représentés sur le plan ci-dessus. Le problème consiste à déterminer s'il existe ou non une promenade dans les rues de Königsberg permettant, à partir d'un point de départ au choix, de passer une et une seule fois par chaque pont, et de revenir à son point de départ, étant entendu qu'on ne peut traverser le Pregel qu'en passant sur les ponts. Le problème mathématique se présente de la façon suivante : Une telle promenade n'existe pas, et c'est Euler qui donna la solution de ce problème en caractérisant les graphes que l'on appelle aujourd'hui « eulériens » en référence à l'illustre mathématicien, à l'aide d'un théorème dont la démonstration rigoureuse ne fut en fait publiée qu'en 1873, par Carl Hierholzer. Ce problème n'a sous cette forme non généralisée qu'un intérêt historique, car pour ce cas, il est assez intuitif de démontrer que la promenade demandée n'existe pas. Pour voir cela, il suffit d'associer un graphe à la ville comme dans la figure ci-dessus et de supposer que la promenade recherchée existe. On peut alors, à partir de la promenade, ordonner les sept arêtes du graphe de façon que deux arêtes consécutives par rapport à notre ordre soient adjacentes dans le graphe (en considérant que la dernière et la première arête sont consécutives, puisqu'il y a retour au point de départ). Ainsi tout sommet du graphe est-il nécessairement incident à un nombre pair d'arêtes (puisque s'il est incident à une arête il est aussi incident à l'arête précédente ou qui lui succède dans l'ordre).