Il y a quelques jours, je rédigeais un billet sur le thème de l'élégance et l'illustrais à travers l'exemple de deux ponts. Aujourd'hui, je souhaite vous parler de ponts, des problèmes que les gens peuvent se poser à leur sujet et de l'élégance déployée par certains esprits pour aider à la résolution desdits problèmes.
Pour ce faire, je vous invite à vous projeter dans le passé et dans une ville qui n'existe plus en tant que telle : à Königsberg au milieu du XVIIIè siècle. Vous voilà à quelques encablures de la mer Baltique, dans une cité prussienne florissante, joyau des villes hanséatiques. Quelques esprits y brillent (Kant, Euler) dans un siècle dit des "lumières".
La ville de Königsberg (aujourd'hui Kaliningrad, capitale de la région russe éponyme, véritable enclave en plein milieu de la communauté européenne) comptait alors sept ponts. Ces ponts reliaient les différentes rives du fleuve Pregel conformément au schéma ci-dessous :
A cette époque régnait calme et prospérité. Ce climat propice donnait aux habitants de Königsberg l'opportunité de rivaliser d'ingéniosité dans l'énoncé d'énigmes, de petits problèmes à résoudre entre amis. Parmi eux, il en était un concernant les ponts de la cité :
"Peut-on traverser d'une seule traite les 7 ponts de la ville sans avoir à repasser par l'un d'entre eux ?"
Comme personne n'était en mesure de trouver la solution, la municipalité décida, plus d'un siècle plus tard, en 1875, de construire un huitième pont, ce qui permit de résoudre le problème une fois pour toutes.
Pourtant en 1736, un certain Euler avait fourni la preuve mathématique formelle de l'inexistence d'un chemin permettant de répondre à la question posée. Cette preuve est d'une élégance rare en ce qu'elle peut être comprise par n'importe qui, même un enfant sans le moindre bagage mathématique.
Si vous changez la représentation du problème en remplaçant chaque parcelle de terre par un gros point noir qu'on appellera un noeud et chaque pont par une courbe reliant deux noeuds qu'on désignera sous le terme d'arc, vous obtenez le schéma suivant :
La preuve est fondée sur une observation toute simple. Les noeuds d'où part un nombre impair d'arcs doivent être soit le point de départ, soit le point d'arrivée du périple. Par conséquent, il ne doit pas y en avoir plus de deux. Or, combien y a-t-il de noeuds avec un nombre impair d'arcs dans le cas de Königsberg ? 4. Cela fait 2 de trop. Il n'y a donc pas de solution.
Vous remarquerez par ailleurs que le fait de construire un huitième pont, à quelqu'endroit que ce soit, permet de réduire le nombre de noeuds impairs de 4 à 2. Il suffit désormais de partir d'un noeud impair, de traverser tous les ponts des noeuds pairs, pour finir sur l'autre noeud impair. Le tour est dans le sac.
En musant dans la blogosphère, j'ai trouvé une autre démonstration du problème des ponts de Königsberg, tout aussi élégante, puisqu'elle ne s'appuie que sur des combinaisons simples de chiffres et de lettres. Si vous êtes curieuse ou curieux d'en prendre connaissance, c'est ici. Croyez-moi, cela vaut le détour.
Pourtant, ce que je trouve le plus remarquable dans la façon dont Euler a résolu le problème des ponts, c'est son changement de représentation, sa manière de redessiner les contours de la situation, d'en renommer les éléments clés, sa modélisation, en somme. En introduisant les notions simples de noeuds et d'arcs, il donnait naissance à une branche nouvelle des mathématiques connue désormais sous le nom de théorie des graphes. La théorie des graphes est essentielle pour comprendre les lois associées au développement des réseaux complexes. Et aujourd'hui, c'est sur les chemins de traverse issus de cette théorie que nous batifolons à chaque fois que nous utilisons Internet, le "réseau des réseau".
Chapeau bas, Monsieur Leonhard Euler, et merci !
well, i'll answer you here, 'cause it seems that my blog don't accept my comments. uploading a mp3 file actually depends on your host. instead of uploading a jpeg file i just upload a mp3, that's all, not a particular skill of mine.
Rédigé par : Barbara | 05/01/2007 à 14:11
Merci Barbara ! Après quelques essais infructueux, j'y suis enfin parvenu. Bon week-end !
Rédigé par : Jean-Marc | 05/01/2007 à 20:25
People should read this.
Rédigé par : Kristine | 29/10/2008 à 00:11