ponts de Königsberg

COMBINATOIRE
HISTOIRE DES SCIENCES

Le problème des sept ponts de Königsberg est l’exemple type de graphe eulérien .

La ville de Königsberg (aujourd’hui Kaliningrad) sur la rivière Pregolia comporte deux îles, sept ponts relient les îles entre elles ou aux rives. Euler résolut par la négative le problème de savoir s’il existait une promenade permettant de passer une fois et une seule sur chaque pont.
La modélisation de ce problème a l’intérêt de se généraliser, il est un des points de départ de la théorie des graphes.
La cause est que de chaque île et de chaque rive partent un nombre impair de ponts.
Pour qu’on puisse faire une promenade ramenant au point de départ, le nombre de ponts aurait dû pour chaque île et chaque rive être pair. Si on enlève la contrainte de revenir au point de départ, il aurait fallu que deux des lieux au plus (le départ et l’arrivée) aient un nombre impair de ponts.