Les ponts de Königsberg

lundi 14 avril 2014
par  Webmaster IREM

1 Pont, 2 Ponts, 3 Ponts…

JPEG - 16.7 ko

Un bus pourra-t-il passer sur tous les ponts une fois et une seule et revenir à son point de départ ?

La solution

JPEG - 9.3 ko 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 : GIF - 5.9 ko GIF - 2 ko

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.

GIF - 2.2 ko Un graphe Eulérien :

Cherchez un trajet !


Commentaires

Navigation

Articles de la rubrique

  • Les ponts de Königsberg