Conte d’auteur
graphes nombres visualisation espace
chercher communiquer modéliser représenter
Résumé : Un problème de traversée de ponts qui a mené à la création de la théorie des graphes par Leonhard Euler.
Il était une fois, dans une ville appelée Königsberg, un endroit magnifique situé dans l'ancienne Prusse orientale. La rivière Pregel traversait la ville et la divisait en quatre quartiers distincts : les deux berges et deux îles. Chacun de ces quartiers était relié aux autres par 7 ponts : le pont du forgeron, le pont du connecteur, le pont vert, le pont du marché, le pont de bois, le pont haut et le pont du miel.
Une promenade sur les ponts était toujours un divertissement pour les jeunes. Les citoyens étaient très fiers de ce grand réseau de communication, et un petit jeu est né parmi eux pour se divertir dans les moments d'ennui. Il consistait en une seule question :
— Est-il possible de faire une promenade en partant de n'importe lequel de ces quartiers, en passant par tous les ponts, en ne les traversant qu'une seule fois et en revenant au point de départ ?
Pendant des années, les citoyens ont essayé de trouver un itinéraire qui respecte ces règles. Ils ont dessiné des cartes, tracé des chemins et parcouru la ville, mais personne n'a réussi à résoudre l'énigme.
À cette époque, un éminent mathématicien se trouvait en ville et travaillait à l'Académie prussienne des sciences. Naturellement, il s'intéressa immédiatement à l'énigme et entreprit de trouver une solution. Son nom était Leonhard Euler.
Pour résoudre cette question, il commença par simplifier la carte de Königsberg. Au lieu de penser aux bâtiments et aux rues, il dessina un schéma simple :
— Chaque quartier de la ville est représentée par un point, appelé sommet.
— Chaque pont est représenté par une ligne, appelée arête, reliant deux sommets.
En regardant son dessin, Euler remarqua quelque chose de curieux. Il décida de compter combien de ponts (ou de lignes) atteignaient chaque région (ou point). Il appela ce nombre le degré de chaque sommet.
Il commença à dessiner des itinéraires, mais à chaque fois qu'il essayait de traverser tous les ponts sans se répéter, il se retrouvait toujours bloqué.
Chaque fois qu'il atteignait un cercle, il y avait toujours plus de ponts qu'il n'en fallait pour sortir. Il compta combien de ponts atteignaient chaque cercle. Si le nombre était impair, il était coincé et ne pouvait pas l'utiliser pour sortir ou revenir sans se répéter.
Et c'est ainsi que cela se passait ! À Königsberg, tous les quartiers avaient un nombre impair de ponts connectés. Cela signifie qu'il est impossible de traverser tous les ponts sans devoir passer deux fois par le même.
Euler prouva que ce problème n'avait pas de solution. Sa découverte fut très importante, non seulement parce qu'elle permit de résoudre cette énigme, mais aussi parce qu'elle inventa une nouvelle façon d'étudier les problèmes : la théorie des graphes.
Aujourd'hui, les graphes sont utilisés dans tous les domaines, de la planification des itinéraires de bus à la conception des réseaux internet. Bien que les habitants de Königsberg n'aient pas pu traverser ses ponts comme ils le souhaitaient, ils sont entrés dans une histoire des mathématiques qui continue d'aider le monde.
Ainsi, la ville aux sept ponts et son énigme resteront à jamais dans les livres d'histoire et de mathématiques.