Problème des sept ponts de Königsberg
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (aujourd'hui Kaliningrad). Sa résolution fut recherchée par ses habitants tout au long du XVIIIe siècle.

Le problème est le suivant :

Étant donné que la ville est construite sur deux îles reliées au continent (Le mot continent vient du latin continere pour « tenir ensemble », ou continens terra, les « terres continues ». Au sens propre, ce...) par six ponts, et entre elles par un pont (Un pont est une construction qui permet de franchir une dépression ou un obstacle (cours d'eau, voie de communication, vallée, etc.) en passant par-dessus cette séparation. Le franchissement supporte le passage d'hommes et de...), trouver un chemin quelconque permettant, à partir d'un point (Graphie) de départ au choix, de passer (Le genre Passer a été créé par le zoologiste français Mathurin Jacques Brisson (1723-1806) en 1760.) 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 (L’eau est un composé chimique ubiquitaire sur la Terre, essentiel pour tous les organismes vivants connus.) qu'en passant par les ponts.

Résolution du problème

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 en le ramenant à un problème de la théorie des graphes (Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :). Sa démarche peut être schématisée de cette manière :

Le problème se ramène alors à la recherche (La recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances scientifiques. Par...) d’un cycle eulérien (chaîne passant par toutes les arêtes du graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) 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é (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) impair. Celui de la ville de Königsberg en possède 4 (chaque berge est le départ de 3 ou 5 ponts), le problème n'admet donc pas de solution.

Si le problème avait consisté à n'emprunter les ponts qu'une seule fois sans pour autant revenir à son point de départ, cela reviendrait à la recherche d'une chaîne (Le mot chaîne peut avoir plusieurs significations :) 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 possède 0 ou 2 sommets de degré impair. Dans le deuxième cas, le chemin doit partir d'un des sommets de degré impair, et aboutir à l'autre sommet de degré impair.

Page générée en 0.132 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique