Problème des sept ponts de Königsberg
Les sept ponts de Königsberg est un problème mathématique historiquement célèbre. Leonhard Euler a résolu le problème en 1735. Cela a conduit au début de la théorie des graphes. Cela a ensuite conduit au développement de la topologie.
La ville de Königsberg en Prusse (aujourd'hui Kaliningrad, Russie) était située des deux côtés de la rivière Pregel. Elle comprenait deux grandes îles qui étaient reliées entre elles et au continent par sept ponts.
Le problème était de trouver un moyen de se promener dans la ville en traversant chaque pont une fois et une seule. Les îles ne pouvaient être atteintes par aucune autre voie que les ponts. Chaque pont devait être traversé complètement à chaque fois. La promenade ne doit pas nécessairement commencer et se terminer au même endroit. Euler a prouvé que le problème n'a pas de solution.
Carte de Königsberg à l'époque d'Euler montrant le tracé réel des sept ponts, en mettant en évidence la rivière Pregel et les ponts
L'analyse d'Euler
Tout d'abord, Euler a souligné que le choix de la route à l'intérieur de chaque masse terrestre n'a pas d'importance. La seule propriété importante d'un itinéraire est l'ordre dans lequel les ponts sont franchis. Il a donc modifié le problème en termes abstraits. Cela a jeté les bases de la théorie des graphes. Il a supprimé toutes les caractéristiques sauf la liste des masses terrestres et les ponts qui les relient. Dans le langage de la théorie des graphes, il a remplacé chaque masse terrestre par un "sommet" ou un nœud abstrait. Puis il a remplacé chaque pont par une connexion abstraite, une "arête". Une arête (route) enregistrait les deux sommets (masses terrestres) qui étaient reliés. De cette façon, il a formé un graphique.
→ →
Le graphique dessiné est une image abstraite du problème. Ainsi, les bords peuvent être joints de n'importe quelle manière. Seul le fait que deux points soient reliés ou non est important. Changer l'image du graphique ne change pas le graphique lui-même.
Ensuite, Euler a observé que (sauf aux extrémités de la marche), chaque fois que l'on entre dans un sommet par un pont, on le quitte par un pont. Dans toute marche du graphique, le nombre de fois que l'on entre dans un sommet est égal au nombre de fois que l'on en sort. Si chaque pont a été franchi exactement une fois, il s'ensuit que, pour chaque masse terrestre (à l'exception de celles choisies pour le départ et l'arrivée), le nombre de ponts touchant cette masse terrestre doit être pair. En effet, s'il y a n ponts, il est franchi exactement 2n fois. Cependant, les quatre masses terrestres du problème initial sont toutes touchées par un nombre impair de ponts (un pont est touché par 5 ponts, et chacun des trois autres par 3). Il y a tout au plus deux masses qui peuvent être les points d'arrivée d'une marche. Ainsi, la proposition d'une marche traversant chaque pont une fois conduit à une contradiction.
En langage moderne, Euler montre que la possibilité ou non de parcourir un graphe en franchissant une fois chaque arête dépend des degrés des nœuds. Le degré d'un nœud est le nombre d'arêtes qui le touchent. Euler montre qu'une condition nécessaire pour la marche est que le graphe soit connecté et ait exactement zéro ou deux nœuds de degré impair. Ce résultat énoncé par Euler a été prouvé par la suite par Carl Hierholzer. Une telle marche est maintenant appelée chemin eulérien ou marche d'Euler. S'il y a des nœuds de degré impair, alors tout chemin eulérien commence à l'un d'entre eux et se termine à l'autre. Comme le graphique représentant le Königsberg historique comporte quatre nœuds de degré impair, il ne peut pas avoir de chemin eulérien.
Le travail d'Euler a été présenté à l'Académie de Saint-Pétersbourg le 26 août 1735. Il a été publié sous le titre Solutio problematis ad geometriam situs pertinentis (La solution d'un problème relatif à la géométrie de la position) dans la revue Commentarii academiae scientiarum Petropolitanae en 1741. Il est disponible en anglais dans The World of Mathematics.
Importance dans l'histoire des mathématiques
Dans l'histoire des mathématiques, la solution d'Euler du problème du pont de Königsberg est considérée comme le premier théorème de la théorie des graphes. La théorie des graphes est un sujet désormais généralement considéré comme une branche de la combinatoire.
État actuel des ponts
Deux des sept ponts d'origine ont été détruits lors du bombardement de Königsberg pendant la Seconde Guerre mondiale. Deux autres ont été démolis par la suite. Ils ont été remplacés par une autoroute moderne. Les trois autres ponts subsistent, bien que seuls deux d'entre eux datent de l'époque d'Euler (l'un d'eux a été reconstruit en 1935). Ainsi, en 2000, il y avait cinq ponts à Kaliningrad.
En termes de théorie des graphes, deux des nœuds ont maintenant un degré 2, et les deux autres un degré 3. Par conséquent, un chemin eulérien est maintenant possible, mais comme il doit commencer sur une île et se terminer sur l'autre, il est peu pratique pour les touristes.
Pages connexes
- Le jeu Icosian
- Chemin Hamiltonien
- Eau, gaz et électricité
- Problème du voyageur de commerce
Questions et réponses
Q : Quel est le problème des sept ponts de Königsberg ?
R : Les sept ponts de Königsberg est un célèbre problème mathématique qui consiste à trouver un moyen de traverser la ville en empruntant chacun de ses sept ponts une fois et une seule.
Q : Qui a résolu le problème des sept ponts de Königsberg ?
R : Leonhard Euler a résolu le problème des sept ponts de Königsberg en 1735.
Q : À quoi a conduit la solution du problème des sept ponts de Königsberg ?
R : La solution du problème des sept ponts de Königsberg a conduit au début de la théorie des graphes, qui a ensuite conduit au développement de la topologie.
Q : Où se trouve Königsberg ?
R : Königsberg est situé en Prusse, qui fait aujourd'hui partie de Kaliningrad, en Russie.
Q : Quel était le plan de Königsberg ?
R : Königsberg s'étendait de part et d'autre de la rivière Pregel et comprenait deux grandes îles reliées l'une à l'autre et au continent par sept ponts.
Q : Quelles étaient les conditions requises pour résoudre le problème des sept ponts de Königsberg ?
R : Le problème consistait à trouver un moyen de parcourir la ville en traversant chaque pont une fois et une seule, chaque pont devant être traversé complètement à chaque fois. Les îles ne pouvaient être atteintes par aucun autre chemin que les ponts, et la promenade ne devait pas nécessairement commencer et se terminer au même endroit.
Q : Euler a-t-il prouvé que le problème des sept ponts de Königsberg avait une solution ?
R : Non, Euler a prouvé que le problème des sept ponts de Königsberg n'a pas de solution.
