Les ponts de Königsberg
par
1 Pont, 2 Ponts, 3 Ponts…
Un bus pourra-t-il passer sur tous les ponts une fois et une seule et revenir à son point de départ ?
Ce problème est connu dans l’histoire comme le problème des sept ponts de Königsberg
Il a été résolu par Euler et est considéré comme un des problèmes à l’origine de la théorie des graphes.
Peut on se promener en passant une fois et une seule par tous les ponts ?
La réponse est non.
Cette configuration des ponts de Königsberg se modélise par un graphe :
Les arcs symbolisent les parcours possibles entre les différents secteurs de la ville.
Euler a démontré que, pour qu’un trajet passe une fois et une seule sur chaque arête et revienne au point de départ, il est nécessaire que tous les nœuds du graphe soient reliés à un nombre pair d’arête. Un tel graphe est dit eulérien.
Un graphe Eulérien :
Cherchez un trajet !
Commentaires