1 Problème des sept ponts de Königsberg[modifier]
Le problème des sept ponts de Königsberg est une énigme mathématique et topologique classique qui a donné naissance à la théorie des graphes et servit de base au concept moderne de chemin eulérien. Cette célèbre question concerne la possibilité de traverser tous les ponts de la ville de Königsberg, en Prusse (aujourd'hui Kaliningrad, Russie), une fois et une seule, sans jamais passer deux fois par le même pont.
1.1 Origine historique du problème des sept ponts de Königsberg[modifier]
Située sur le fleuve Pregel, la ville de Königsberg était divisée en quatre parties reliées par sept ponts. Les habitants se demandaient s'il était possible de faire une promenade traversant chacun de ces ponts une seule fois.
Le problème fut officiellement étudié en 1736 par le mathématicien suisse Leonhard Euler, qui publia une solution révolutionnaire posant les bases des graphes mathématiques.
1.2 Formulation mathématique et solution de Euler[modifier]
Euler modélisa la ville sous forme d'un graphe où les îles et berges correspondaient à des nœuds (ou sommets) et les ponts à des arêtes (ou liens). Il démontra que la promenade demandée, appelée chemin eulérien, existait seulement si le graphe avait zéro ou deux sommets de degré impair.
Dans le cas des sept ponts de Königsberg, tous les sommets avaient un degré impair, rendant donc impossible une telle promenade.
1.2.1 Principes clés du chemin eulérien[modifier]
- Un chemin eulérien traverse chaque arête exactement une fois.
- Un cycle eulérien est un chemin eulérien qui commence et finit au même sommet.
- Le problème des sept ponts de Königsberg est le premier exemple célèbre qui a motivé ces définitions.
1.3 Importance dans l'histoire des mathématiques et de la théorie des graphes[modifier]
Le problème des sept ponts de Königsberg marque le point de départ de la théorie des graphes, une branche fondamentale des mathématiques et de l'informatique. L'approche d'Euler est considérée comme la première preuve rigoureuse en topologie et ouvre la voie à :
- L'étude des réseaux.
- L'algorithmique moderne.
- Les applications dans la planification, la logistique, et plus généralement dans l'optimisation.
1.4 Représentations visuelles et pédagogiques[modifier]
Cette carte illustre la configuration originale des ponts reliant les différentes parties de la ville.
1.5 Voir aussi[modifier]
1.6 Références[modifier]
- ↑ Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum imperialis Petropolitanae, 8, 128–140.
- ↑ Gross, J., & Yellen, J. (2005). Graph Theory and Its Applications. CRC Press.
- ↑ West, D. B. (2001). Introduction to Graph Theory (2nd ed.). Prentice Hall.