D’un problème de ponts à une recherche sur Google

– Mathscope, Faculté des Sciences; © Jacques Erard –

Connaissez-vous la ville de Königsberg et ses sept ponts?Pourtant, le problème de savoir s’il est possible de parcourir tous ses ponts sans passer deux fois par le même est la première pierre de la théorie mathématique qui se cache sous chacune de vos recherches sur Google!

Lorsqu’en 1736 Euler démontra qu’il est impossible de parcourir les sept ponts de Königsberg sans passer deux fois par le même pont, il était loin de se douter qu’il venait de créer un outil puissant permettant de faire des recherches rapides et pertinentes sur un ensemble aussi vaste que le réseau internet. Le problème des ponts de Königsberg est en effet à la base de la théorie des graphes, outil sous-jacent des moteurs de recherche sur le web.

En mathématiques, un graphe est un ensemble de points, les sommets, reliés par des segments, les arêtes. Le fait de connaître certaines caractéristiques (nombre d’arêtes en chaque sommet, nombre de composantes connexes, …) permet de déduire des propriétés générales sur le graphe (p. ex. le fait de pouvoir ou non parcourir le graphe sans passer deux fois par la même arête).

Un graphe permet de décrire efficacement les relations entre des objets. On peut par exemple établir le graphe d’internet : les sommets représentent les pages et les arêtes les liens hypertexte. Le graphe obtenu est bien sûr énorme, mais en utilisant des techniques de probabilités comme les marches aléatoires, on peut déduire des informations sur l’importance de certaines pages par rapport à d’autres et trouver ainsi la meilleure page correspondant à une recherche sur internet.

De nos jours, Königsberg s’appelle Kaliningrad et les sept ponts ont tous été détruits ou remplacés, mais si vous souhaitez expérimenter une visite de la ville, venez au Mathscope !

Références

1. L. Euler, Solutio problematis ad geometriam situs pertinentis, Mémoires de l'Académie des sciences de Berlin, pp. 128-140, 1759. Disponible en libre accès

Pour aller plus loin

• Atelier du Mathscope: Promenade à Königsberg

Explorer l'invisible