Les sept ponts de Königsberg

Au XVIIIᵉ siècle, les habitants de Königsberg ont longtemps cherché à résoudre une énigme : la ville est traversée par la rivière Pregolia, qui forme deux îles. Sept ponts mènent aux îles par-dessus cette rivière. Est-il possible, au cours d’une seule promenade du dimanche, de traverser tous les ponts, mais chacun exactement une fois ? Regardons comment les ponts étaient disposés au-dessus de la rivière :

Est-il possible de commencer notre promenade quelque part et de traverser tous les ponts exactement une fois ? On peut essayer : on commence en bas à gauche, on va vers le haut, puis peu à peu vers la droite, comme ceci :

On voit qu’on a traversé six ponts sur sept, un des ponts nous a échappé. On peut essayer un autre chemin…

Là encore, on n’a traversé que six des sept ponts de notre Königsberg. On a presque l’impression qu’il est impossible de traverser chaque pont exactement une fois en une seule promenade. Un jour, le célèbre mathématicien Leonhard Euler est tombé sur ce problème. Célèbre, c’est peu dire – Euler était une véritable légende des mathématiques, qui a même donné son nom au nombre d’Euler. Euler s’est dit qu’il allait venir à bout de cette énigme. Il a commencé par nommer les différentes îles, ou parties de la ville, que reliaient les ponts :

Euler a alors fait le raisonnement suivant : si un nombre pair de ponts mène à une île, on peut traverser ces ponts au cours d’une seule promenade, où qu’on commence. En somme, on arrive sur l’île par un pont, on repart par un autre – le nombre de ponts qu’il reste à traverser a diminué de deux. Pour pouvoir arriver sur l’île par un pont et repartir par un autre, il faut deux ponts. Si six ponts mènent à une île, on visite l’île trois fois. Par exemple, imaginons que quatre ponts mènent à l’île B, de cette façon :

On peut alors traverser tous les ponts au cours d’une seule promenade du dimanche, où qu’on commence. Essaie ! Sur la figure, j’ai marqué un chemin. Imaginons maintenant qu’un pont de plus mène à l’île B, depuis l’île D :

On voit que le chemin que nous avons choisi ne nous permet pas de traverser tous les ponts exactement une fois. Il faudrait revenir sur l’île B par un des ponts, puis passer sur l’île D. Mais nous pouvons choisir un autre chemin. Nous pouvons commencer notre promenade sur l’île B et nous sommes alors capables de traverser tous les ponts exactement une fois :

Nous avons commencé notre promenade sur l’île B, nous sommes montés vers la zone A, puis nous sommes revenus par un pont sur B, nous sommes allés vers la zone C, puis nous sommes revenus sur l’île B et enfin nous sommes allés sur l’île D. Ainsi, si l’on commence sur une île à laquelle mène un nombre impair de ponts, on est capable de traverser tous ses ponts exactement une fois. Ou bien on peut faire tout le contraire – on peut commencer sur l’île D et finir sur l’île B.

Euler a ainsi remarqué que, pour qu’il soit possible de traverser tous les ponts exactement une fois, il faut que toutes les îles aient un nombre pair de ponts, ou alors qu’il y ait deux îles avec un nombre impair de ponts – on commence sur l’une des îles à nombre impair de ponts et on finit sur l’autre. Toutes les autres îles doivent avoir un nombre pair de ponts. Si l’on regarde les sept ponts d’origine à Königsberg :

on voit que chaque île a un nombre impair de ponts ! L’île A en a 3, B en a 5, C en a 3 et D en a aussi 3. C’est pourquoi l’énigme n’a pas de solution – il est impossible de traverser les sept ponts exactement une fois au cours d’une seule promenade du dimanche. Si l’on détruisait n’importe lequel des ponts, l’énigme aurait soudain une solution. Détruisons, par exemple, un des ponts entre les îles B et C :

On voit que l’île B a tout à coup 4 ponts et l’île C deux ponts. Le nombre de ponts des îles A et D n’a pas changé. On a soudain deux îles avec un nombre pair de ponts et deux îles avec un nombre impair de ponts. Si l’on commence notre promenade sur l’une des îles qui ont un nombre impair de ponts, on peut traverser tous les ponts exactement une fois. Sur la figure, nous avons commencé sur l’île A et fini sur l’île D.

Leonhard Euler a donc résolu un autre célèbre problème mathématique et il a, plus ou moins, posé les bases de ce que l’on appelle aujourd’hui la théorie des graphes ; en son honneur, un graphe dans lequel on peut parcourir toutes les arêtes exactement une fois s’appelle, dans le langage de la théorie des graphes, un graphe eulérien.