|
Königsberg
° Ponts de Königsberg. –
Récréation
posée en 1736 et résolue par Leonhard Euler (1707-1783) : La ville de Königsberg est reliée à la terre ferme par sept ponts. On doit
tracer un itinéraire partant d'un point quelconque de la ville et permettant de
traverser une et une seule fois chacun des sept ponts pour revenir au point de
départ.
Le problème consiste à déterminer s'il existe un chemin
ne passant qu'une
seule fois par chaque ligne du graphe associé à ce problème. Euler a
démontré qu'il était impossible de tracer un tel chemin. Ce problème
est à l'origine de la théorie des graphes. Voici le graphe correspondant reproduit d'abord sur le schéma,
puis seul :
Les lignes représentent les ponts. Les nœuds représentent les rives et
les îles. La règle d'Euler est simple. On compte le nombre de ponts
aboutissant à chaque rive. Si plus de deux résultats sont impairs, il n'y a
pas de solution. Par ailleurs, si tous les résultats sont pairs ou si deux
seulement sont impairs, il existe au moins une solution.
Aussi appelés ponts
de Kaliningrad qui est le nom donné en 1946 à cette ville de la Russie. Ce problème appartient à la classe des récréations
topologiques.
© Charles-É. Jean
Index
: J-K
|
