Sur le Pregel, fleuve qui traverse Koenigsberg, ancienne ville allemande de Prusse orientale qui s'est longtemps appelée Kaliningrad, se trouvent deux îles, reliées entre elles et aux rives par sept ponts (figure 1).
figure 1
figure 2
Au XVIIe siècle, un curieux s'est posé la question suivante; "est-il possible de traverser chacun des sept ponts en ne passant qu'une fois sur chacun ?"
Pour répondre, on peut "oublier" la carte et mettre en évidence les informations qui comptent : on obtient ce que l'on nomme un graphe, ici avec 7 arcs et 4 sommets (figure 2).
Sur un tel graphe, le problème consiste à dessiner un parcours en n'empruntant chaque arc qu'une seule fois (mais on y peut passer plusieurs fois par chaque sommet).
C'est le mathématicien Léonard Euler qui, au XVIIIe, énonça un critère pour qu'un graphe "planaire" contienne un tel parcours, que l'on nomme désormais "circuit Eulérien".
Parmi les cinq graphes ci dessous, quel est celui qui modélise le problème des sept ponts ? Quels sont ceux que l'on peut tracer sans lever le crayon sans repasser deux fois sur le même arc.
En tentant un classement des sommets, formule, comme Euler, une conjecture permettant de distinguer les graphes où existe un circuit éponyme.
Teste ta conjecture sur quelques graphes de ton cru.
Essaie de la justifier.
Peux-tu alors préciser quels sont les graphes qui admettent un "cycle Eulérien", c'est à dire un circuit Eulérien où les sommets de départ et d'arrivée coïncident ?
