Vous aurez beaucoup de mal à trouver
Königsberg sur une carte moderne
mais une particularité géographique
a fait d'elle l'une des villes
les plus célèbres des mathématiques.
Cette ville médiévale allemande
était traversée par la rivière Pregel.
En son centre, il y avait
deux grandes îles.
Ces deux îles étaient reliées
entre elles et aux berges
par sept ponts.
Carl Gottlieb Ehler, un mathématicien
devenu ensuite maire d'une ville proche,
en fit son idée fixe.
Il en revenait toujours
à la même question :
quel trajet permettrait à quelqu'un
de traverser l'ensemble des sept ponts
en ne les franchissant chacun
qu'une seule fois ?
Réfléchissez-y un instant.
7
6
5
4
3
2
1
Vous jetez l'éponge ?
Vous devriez.
C'est impossible.
En tentant d'expliquer pourquoi,
le célèbre mathématicien Leonhard Euler
inventa une nouvelle branche
des mathématiques.
Carl écrivit à Euler
pour lui demander son aide.
Dans un premier temps,
Euler écarta le problème,
qui ne concernait pas les maths.
Mais plus il s'interrogeait,
plus il lui semblait que finalement,
il y avait là quelquechose.
Il trouva la réponse
grâce à une branche de la géométrie
qui n'existait pas encore
et qu'il nomma Géométrie de position,
désormais connue comme
la Théorie des graphes.
La première idée d'Euler
était que le trajet emprunté pour entrer
sur une île ou une berge et la quitter
n'avait pas vraiment d'importance.
Donc, la carte pouvait être simplifiée
en représentant les quatre zones de terre
par un simple point,
que nous appellerons nœud,
reliés par des lignes ou des arcs
représentant les ponts.
Ce graphe simplifié nous permet de compter
facilement les degrés de chaque nœud.
C'est-à-dire le nombre de ponts
partant de chaque rive.
Pourquoi les degrés sont-ils importants ?
Selon les règles du défi,
une fois arrivé sur la terre par un pont,
le voyageur doit en repartir
par un autre pont.
Autrement dit, les ponts menant
d'un nœud à un autre
doivent, pour chaque parcours,
aller par paire,
ce qui signifie que le nombre de ponts
menant aux différentes berges visitées
doit être pair.
Les seules exceptions possibles
seraient le point de départ
et d'arrivée du trajet.
Sur le graphe, on voit que
les quatre nœuds ont un degré impair.
Du coup, peu importe le trajet choisi,
à un moment ou à un autre, l'un des ponts
devra être traversé deux fois.
Euler mit cette preuve à profit
pour formuler une théorie générale
s'appliquant à tous les graphes
comportant au moins deux nœuds.
Un chemin eulérien ne passant
qu'une fois par chaque sommet
n'est possible
que dans un cas sur deux.
Dans le premier, il y a exactement
deux nœuds de degré impair,
tous les autres étant donc pairs.
Dans ce cas là, le point de départ
est l'un des nœuds impairs
et l'autre, le point d'arrivée.
Dans le deuxième cas, tous les nœuds
sont de degré pair.
Le chemin eulérien commence
et s'achève alors au même point ;
de fait, on le nomme également
cycle eulérien.
Du coup, comment créer
un chemin eulérien à Königsberg ?
C'est simple.
Il suffit de supprimer l'un des ponts.
Et il s'avère que l'Histoire
en a elle-même créé un.
Pendant la seconde guerre mondiale,
les forces aériennes soviétiques
ont détruit deux des ponts de la ville,
ouvrant la voie à un chemin eulérien.
Mais, pour être honnête, ce n'était
sans doute pas intentionnel.
Ces bombardement ont pratiquement
rayé Königsberg de la carte.
Elle fut ensuite reconstruite pour devenir
la ville russe de Kaliningrad.
Königsberg et ses sept ponts
ne sont peut-être plus aujourd'hui,
mais ils resteront dans l'Histoire
comme l'énigme en apparence triviale
à l'origine d'une branche complètement
nouvelle des mathématiques.