Garçon devant un ordinateur.jpg
LeSavant.svg

la cabane  •  le Savant  •  le Livre d'or

Participez ! Cet article, comme tous les articles de Vikidia, est peut-être incomplet et tu peux l'améliorer. Tu as des connaissances sûres sur le sujet (texte ou illustration) ? Alors n'hésite pas à les ajouter. Ta contribution est la bienvenue ! C'est à toi de jouer ! Clin d'œil

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
Les sept ponts de Königsberg

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]

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]

Le problème mathématique historique[modifier]

É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]

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