Histoire des mathématiques Problème

problème des sept ponts de Königsberg

Problème

problème mathématique célèbre

domaine
théorie des graphes

Pour comprendre

rédaction

Traverser chaque pont une seule fois

Le problème des sept ponts de Königsberg demande s'il est possible de traverser chacun des sept ponts une seule fois. La difficulté ne dépend pas des distances, de la forme des rives ou de la longueur des trajets. Seules comptent les liaisons entre les quatre rives.

On peut donc remplacer la ville par un schéma plus simple : chaque rive devient un point et chaque pont devient une liaison entre deux points. Cette réduction conserve exactement l'information utile pour répondre à la question.

Compter les liaisons de chaque rive

Dans ce graphe, chaque rive touche un nombre impair de ponts. Or un trajet qui entre sur une rive doit normalement en repartir : les passages s'y organisent donc par paires, sauf éventuellement au début ou à la fin du parcours.

Il ne peut y avoir que deux exceptions, correspondant aux deux extrémités d'un trajet. Ici, les quatre rives ont un nombre impair de liaisons. Il est donc impossible de traverser les sept ponts une seule fois chacun. Cette résolution est considérée comme l'acte de naissance de la théorie des graphes.

Repères historiques

  • résolu par Euler en 1736

La figure réduit les rives et les ponts à un graphe.

{ "boundingBox": [ 0, 4.2, 4.4, -0.2 ], "axis": false, "segments": [ { "from": [ 1.92, 3.48 ], "to": [ 1.12, 2.08 ], "color": "#dc2626", "width": 2 }, { "from": [ 2.08, 3.32 ], "to": [ 1.28, 1.92 ], "color": "#dc2626", "width": 2 }, { "from": [ 1.92, 0.52 ], "to": [ 1.12, 1.92 ], "color": "#dc2626", "width": 2 }, { "from": [ 2.08, 0.68 ], "to": [ 1.28, 2.08 ], "color": "#dc2626", "width": 2 }, { "from": [ 2, 3.4 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 }, { "from": [ 2, 0.6 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 }, { "from": [ 1.2, 2 ], "to": [ 3.2, 2 ], "color": "#dc2626", "width": 2 } ], "points": [ { "x": 2, "y": 3.4, "name": "N", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 2, "y": 0.6, "name": "S", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 1.2, "y": 2, "name": "I", "color": "#1e3a8a", "size": 3, "fixed": true }, { "x": 3.2, "y": 2, "name": "E", "color": "#1e3a8a", "size": 3, "fixed": true } ], "labels": [ { "x": 0.4, "y": 3.8, "text": "7 ponts, 4 rives", "color": "#1e3a8a" } ] }

Dates

demonstration
résolu par Euler

Sources