Problème des sept ponts de Königsberg

Problème des sept ponts de Königsberg

54°42′12″N 20°30′56″E / 54.70333, 20.51556 Le problème des sept ponts de Königsberg est un problème mathématique connu pour être à l'origine de la théorie des graphes. Résolu par Leonhard Euler, il se présente de la façon suivante :

_→_Konigsberg bridges.png7 bridges.svgKonigsburg graph.svg

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. 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.

Résolution du problème

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.

Ce problème n'a qu'un intérêt historique, et absolument aucun intérêt mathématique en dehors de sa généralisation à tous les graphes, 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 à ce 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). Mais le graphe a des sommets qui sont incidents à trois arêtes, d'où l'impossibilité.

Notons que même si on renonce à exiger le retour au point de départ, une promenade traversant une et une seule fois chaque pont n'existe pas. Elle existerait si au plus deux sommets du graphe, correspondant aux points à choisir respectivement comme départ et arrivée, étaient incidents à un nombre impair d'arêtes. Or les sommets du graphe des ponts de Königsberg sont tous les quatre dans ce cas, on est donc loin du compte. Il suffirait cependant de supprimer ou de rajouter un pont quelconque pour que le graphe modifié permette des promenades tous ponts sans retour (seuls deux sommets restant d'incidence impaire). Et ce sont au moins deux ponts, bien choisis, qu'il faudrait ajouter ou retirer pour permettre la promenade avec retour initialement visée.

Sources

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème des sept ponts de Königsberg de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Probleme des sept ponts de Konigsberg — Problème des sept ponts de Königsberg Le problème des sept ponts de Königsberg est le suivant : → → La ville de Königsberg (aujourd hui Kaliningrad) est construite autour de deux îl …   Wikipédia en Français

  • Problème des sept ponts de königsberg — Le problème des sept ponts de Königsberg est le suivant : → → La ville de Königsberg (aujourd hui Kaliningrad) est construite autour de deux îl …   Wikipédia en Français

  • Sept ponts de Königsberg — Problème des sept ponts de Königsberg Le problème des sept ponts de Königsberg est le suivant : → → La ville de Königsberg (aujourd hui Kaliningrad) est construite autour de deux îl …   Wikipédia en Français

  • Problème des missionnaires et des cannibales — Problèmes de passage de rivière Sommaire 1 Historique 2 Les problèmes 2.1 Le détachement 2.2 Le Chien, la Chèvre et les choux …   Wikipédia en Français

  • Problème des neuf points — Thinking outside the box Sans lever le crayon, comment relier les neuf points à l aide de seulement quatre traits droits qui se touchent ? Thinking outside the box signifie, en anglais américain, penser différemment, de façon non… …   Wikipédia en Français

  • Konigsberg — Kaliningrad Pour les articles homonymes, voir Koenigsberg (homonymie). Kaliningrad Калининград …   Wikipédia en Français

  • Königsberg — Kaliningrad Pour les articles homonymes, voir Koenigsberg (homonymie). Kaliningrad Калининград …   Wikipédia en Français

  • Graphe (théorie des graphes) — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Theorie des graphes — Théorie des graphes  Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une branche commune à l informatique et aux mathématiques étudiant les graphes et les objets qui lui… …   Wikipédia en Français

  • Théorie des graphes — Pour la notion mathématique utilisée en Théorie des ensembles, voir Graphe d une fonction. La théorie des graphes est une théorie informatique et mathématique. Les algorithmes élaborés pour résoudre des problèmes concernant les objets de cette… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”