Quel mathématicien et physicien a résolu l'énigme des ponts de Königsberg ?

Au XVIIIe siècle, la ville de Königsberg, alors située en Prusse, était traversée par le fleuve Pregel et organisée autour de deux rives et de deux îles. Sept ponts reliaient ces différentes parties de la ville. Le défi consistait à parcourir la ville en franchissant chacun des sept ponts une seule fois. Contrairement à une formulation souvent reprise, il n’était pas nécessaire de revenir au point de départ. Le mathématicien et physicien suisse Leonhard Euler démontra pourtant qu’un tel parcours était impossible.

Une ville transformée en schéma

Pour résoudre le problème, Euler abandonna les détails géographiques sans importance pour le parcours : la longueur des ponts, leur orientation ou la forme des îles. Il représenta chacune des quatre zones terrestres par un sommet et chacun des sept ponts par une arête reliant deux sommets. Cette manière de traduire une situation concrète en un réseau abstrait constitue l’une des premières grandes étapes vers la théorie des graphes. Le problème ne relevait donc plus seulement de la géographie de Königsberg, mais de la structure des connexions entre les différentes zones.

Le rôle décisif de la parité

Euler observa qu’une zone située au milieu du trajet doit normalement être atteinte par un pont, puis quittée par un autre. Les ponts utilisés dans une telle zone se regroupent donc par paires : un passage pour entrer et un passage pour sortir. Seuls le point de départ et le point d’arrivée peuvent éventuellement présenter un nombre impair de ponts utilisés. Dans un réseau connexe, un parcours empruntant chaque arête exactement une fois ne peut ainsi exister que si aucun sommet n’est impair, lorsque le parcours revient à son point de départ, ou si exactement deux sommets sont impairs, lorsque ses extrémités sont différentes.

Pourquoi le parcours est impossible

Dans le réseau des ponts de Königsberg, les quatre zones terrestres possèdent respectivement 3, 3, 3 et 5 ponts qui leur sont reliés. Elles ont donc toutes un degré impair. Or un parcours ouvert ne peut comporter que deux extrémités, et ne peut donc accommoder que deux sommets impairs au maximum. La présence de quatre sommets impairs suffit à établir l’impossibilité du trajet demandé. Il est par conséquent impossible de franchir les sept ponts une seule fois sans devoir repasser par au moins un d’entre eux.

Un résultat fondateur

Euler exposa cette démonstration dans un mémoire consacré à la géométrie de situation, daté de 1736. Son raisonnement ne fournit pas un itinéraire : il prouve qu’aucun itinéraire satisfaisant les règles ne peut exister. Cette distinction entre la recherche d’un chemin et la démonstration de son impossibilité est essentielle. En étudiant les sommets, les arêtes et la parité de leurs degrés, Euler a posé l’un des fondements de la théorie des graphes, une branche des mathématiques qui analyse les réseaux et leurs relations indépendamment de leur apparence géométrique. Le problème des ponts de Königsberg est ainsi devenu un exemple classique de la puissance d’une modélisation mathématique appliquée à une situation concrète.