Promenade à Königsberg sur les berges du Pregel. © Gumerov Ildar, Wikimedia commons, DP

Sciences

Königsberg, la ville aux 7 ponts qui a donné naissance à la théorie des graphes

Question/RéponseClassé sous :Mathématiques , Königsberg , théorie des graphes

Une promenade, que les habitants de la ville de Königsberg voulaient faire sans y arriver, est à l'origine d'une théorie mathématique initiée par un grand nom des mathématiques du XVIIIe siècle.

Dans la ville de Königsberg aux sept ponts sur le Pregel, un fleuve. Quelle promenade, quelle théorie et quel mathématicien ? 

Réponse :

La ville de Königsberg est construite autour de deux îles sur un fleuve. Ces deux îles sont reliées entre elles par un pont et six autres ponts relient les rives du fleuve aux îles comme le montre le plan, ci-dessous : 

© Hervé Lehning, tous droits réservés

Les habitants se demandaient si l'on pouvait trouver un circuit de promenade, à travers les rues de Königsberg, en partant d'un point au choix et y revenant mais en traversant une et une seule fois chaque pont ?

Léonhard Euler. © DP

Ce désir pouvait sembler étrange mais le mathématicien et physicien, Leonhard Euler (1707 - 1783) résolut la question en initiant la théorie des graphes. Pour cela, il simplifia le plan de Königsberg en un graphe où les nœuds sont les parties de la ville et les arêtes sont les ponts.

Une telle promenade est-elle possible ? © Hervé Lehning, tous droits réservés

Euler remarqua que, si un trajet existait, de chaque nœud partirait un nombre pair d'arêtes, ce qui n'est pas le cas. La promenade était donc impossible et la théorie des graphes naissait. Depuis, un chemin d'un graphe partant et arrivant au même nœud, en passant une et une seule fois par chaque arête est appelé un cycle eulérien.

À savoir

Au bord de la mer Baltique, Königsberg est l'ancien nom de l'actuelle ville russe de Kaliningrad. Auparavant, elle fit partie du Royaume de Prusse, puis de l'Empire allemand. 

Abonnez-vous à la lettre d'information Mathématiques amusantes : chaque semaine, Futura traite une question de mathématique pour le plaisir des 7 à 77 ans.

!

Merci pour votre inscription.
Heureux de vous compter parmi nos lecteurs !

En savoir plus sur Hervé Lehning

Normalien et agrégé de mathématiques, Hervé Lehning a enseigné sa discipline une bonne quarantaine d'années. Fou de cryptographie, membre de l'Association des réservistes du chiffre et de la sécurité de l'information, il a en particulier percé les secrets de la boîte à chiffrer d'Henri II. 

À découvrir également : L'univers des codes secrets de l'Antiquité à Internet, paru en 2012 chez Ixelles.