Braye-en-Laonnois (Aisne) Canal de l'Oise à l'Aisne, écluse nr 10 de Moulin-Brulé.JPG
Céret -Rue Pierre Brune 2.jpg

la cabane • le Livre d'or
Bonnes vacances ! Ramenez des photos de villages avec L'été des villes Wikipédia ! On pourra s'en servir aussi sur Vikidia

Problème des sept ponts de Königsberg

« Problème des sept ponts de Königsberg » expliqué aux enfants par Vikidia, l’encyclopédie junior
(Redirigé depuis 7 ponts de Königsberg)
Aller à : navigation, rechercher
Carte de Königsberg au temps d'Euler, montrant le schéma réel de disposition des sept ponts.

Le problème des sept ponts de Königsberg est un problème mathématique historique résolu par Leonhard Euler grâce à sa théorie des graphes.

Données géographiques[modifier | modifier le wikicode]

La rivière Pregel a deux affluents qui s’écoulent autour du centre de la ville de Königsberg, en Prusse orientale. Sept ponts relient les diverses rives, dont deux îles.

Euler et les sept ponts de Königsberg[modifier | modifier le wikicode]

Le problème mathématique historique[modifier | modifier le wikicode]

Étant donné que la ville est construite sur deux îles reliées par sept ponts, 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 !).

Sa résolution fut recherchée par ses habitants tout au long du XVIIIe siècle.

Léonhard Euler a montré que le problème des sept ponts de Königsberg n'a pas de solution, en appliquant une méthode de son invention, jetant ainsi les bases de la théorie des graphes.

Démonstration[modifier | modifier le wikicode]

Simplification du problème : les 4 quartiers de Königsberg (nord, sud, est, ouest) et les ponts qui les relient.

Les deux contraintes importantes sont :

  1. Le promeneur doit revenir à son quartier de départ à la fin de son parcours, c’est-à-dire suivre ce qu’on appelle un cycle.
  2. Chaque pont doit être traversé une fois exactement (on appelle aujourd’hui « cycle eulérien » un tel cycle).

Euler a remarqué ceci :

  • chaque pont ne doit être parcouru qu’une fois donc il faut autant de ponts pour quitter un quartier que pour y revenir (sinon l’on ne reviendrait jamais au point de départ) ;
  • il faut donc que chaque quartier comporte un nombre pair de ponts.

Or, dans la ville de Königsberg, tous les quartiers sont reliés aux autres par un nombre impair de ponts. Par conséquent, il n’existe pas de cycle eulérien possible dans cette ville, et le problème de la promenade par les sept ponts n’a pas de solution !


Portail des mathématiques - Les nombres, la géométrie et les grands mathématiciens.

54°42′12″N 20°30′56″E / 54.70333, 20.51556