Le problème des sept ponts de Königsberg
Le problème des sept ponts de Königsberg apparut au XVIIIe siècle lorsque les habitants de cette ville s'interrogèrent sur leurs promenades.
La ville de Königsberg (aujourd'hui Kaliningrad) est située sur la rivière Pregel, et elle possédait sept ponts reliant deux îles et les rives adjacentes. Les habitants se demandaient s'il existait un chemin permettant de traverser chaque pont une seule fois et de revenir au point de départ.
En 1735, le mathématicien suisse Leonhard Euler résolut ce problème en proposant une méthode novatrice. En simplifiant le problème à ses caractéristiques géométriques, Euler a réduit la configuration des ponts à des lignes et des points, jetant ainsi les bases de ce qui deviendrait plus tard la théorie des graphes. Sa solution brillante a démontré que ce problème spécifique n'avait pas de solution.
Un graphe se compose d'un ensemble de sommets et d'arêtes. Dans l'exemple ci-dessous on compte 5 sommets (A, B, C, D, E) et 7 arêtes.
On définit ensuite le degré d'un sommet et comptant les arêtes qui y arrivent. Toujours dans l'exemple précédent le sommet A est de degré 2 et le sommet B de degré 4.
Euler a démontré que, dans un graphe, pour parcourir toutes les arêtes une fois et une seule à partir d'un certain sommet, il faut qu'il y ait exactement deux sommets de degré impair. Si tous les sommets sont de degré pair alors il existe un chemin qui part d'un sommet, qui emprunte qu'une seule fois toutes les arêtes et revient au sommet initial.
Pour résoudre le problème des sept ponts de Königsberg il nous faut décrire la situation géographique à l'aide d'un graphe où chaque pont est une arête et les îles et les rives sont des sommets.
Il nous reste à trouver les degrés de chacun des sommets.
| Sommet | A | B | C | D |
| Degré | 5 | 3 | 3 | 3 |
Nous remarquons qu'il n'y aucun sommet de degré pair, il est donc impossible de trouver une promenade passant par tous les ponts qu'une seule fois.
Ce problème est souvent présenté en introduction à la théorie des graphes et nous proposons dans notre boutique une maquette l'illustrant. Elle peut donc servir de support pédagogique à des élèves ou être tout simplement disposée dans une vitrine ou sur une étagère comme objet de collection.
Vous pouvez également retrouver sur notre site le porte clé lithophane de Leohnard Euler :
