Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Sept ponts de Königsberg

Le problème des sept ponts de Königsberg est un problème mathématique historique, qui fit la célébrité de la ville de Königsberg. Sa résolution fut recherchée par ses habitants tout au long du XVIII^e siècle.

Le problème était le suivant :

Étant donné que la ville est construite sur deux îles reliées au continent par six ponts, et entre elles par un pont, trouver un chemin quelconque 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 l'eau qu'en passant par les ponts.

Le problème était insoluble, et c'est Leonhard Euler qui, le premier, donna à ce problème la première résolution mathématique formelle d’un problème de la théorie des graphes. En effet, le problème est la recherche d’un cycle eulérien (chaîne passant par toutes les arêtes du graphe une et une seule fois, et revenant à son point de départ), ce qui n’est possible que si le graphe associé au problème ne possède aucun sommet de degré impair. Si le problème consiste à n'emprunter les ponts qu'une seule fois sans pour autant revenir à son point de départ, le problème devient la recherche d'une chaîne eulérienne (chaîne passant par toutes les arêtes du graphe une et une seule fois), ce qui n'est possible que si le graphe associé au problème ne possède pas plus de deux sommets de degré impair. Celui de la ville de Königsberg en possède 4.

Carte de Königsberg

Cette carte de Königsberg au temps d'Euler montre l'emplacement des sept ponts (en vert clair) et les branches de la rivière (en bleu ciel).
Les ponts (arêtes) relient les berges (sommets ou nœuds). De chaque sommet (ou berge) partent 3 ou 5 ponts (ou arêtes). Chaque sommet est donc de degré impair, le problème est insoluble.