Accueilretour

Les ponts de Königsberg

Courbes & surfaces

Ensembles, nombres & graphes


Un problème historique et célèbre était posé par la disposition des sept ponts de la ville de Königsberg. Il s'agissait de savoir si un piéton pouvait, en se promenant, traverser chacun des sept ponts une fois et une seule.

Il revient à L. Euler de l'avoir résolu grâce à la théorie des graphes (en faisant progresser celle-ci par la même occasion). Formellement, le graphe plan associé au schéma ci-dessus est le suivant :

... et il s'agit de prouver que ce graphe n'est pas eulérien (n'admet pas de chaîne passant une fois et une seule par chaque arête). 

Euler démontra qu'un graphe plan connexe (d'un seul morceau) est eulérien ssi le nombre de ses sommets de degrés impairs est 0 ou 2, réglant le problème.

Königsberg se nomme maintenant Kaliningrad et ses habitants ont apporté une solution différente au problème, en construisant un huitième pont.

[Dictionnaire des mathématiques, A. Bouvier - M. Georges - F. Le Lionnais, PUF 1993]