Théorie des graphes

[AceVentura]

Bonsoir.
Je suis totalement perdu dans l'exercice qui suit, n'ayant JAMAIS fait de théorie des graphes (j'essaye d'aider quelqu'un en vain ...)

Une grande surface est conçue de telle façon que six secteurs (alimentation, hi-fi, ...) notés A,B,C,D,E et F sont reliés par des allées selon le graphe G ci-dessous :

[CENTER][/CENTER]

Un visiteur désire parcourir l'ensemble des allées en ne passant par celles-ci qu'une seule fois.
Il faut démontrer que son souhait est réalisable et donner l'exemple d'un tel parcours.
Je sollicite votre aide

Merci par avance.

[foufa]

il faux toujours commancer et finir par la sommet ayant un nombre impair d'arrête

[Ben314]

Salut,
Il y a le résultat de "je sais plus qui" caché derrière (c'est le principe de ponts de köningsberg : de mémoire (?) ça s'appelle des parcours eulériens).
Il est trés facile de voir que, s'il existe un parcours qui passe une fois et une seule par chaque arrête, alors, à part pour le sommet de départ et d'arrivé tout les autres sommets doivent avoir un nombre pair d'arrêtes vu que, a chaque "arrivée" sur ce sommet doit correspondre un "départ".
On montre réciproquement que la condition est suffisante si le graphe est connexe (i.e. on peut aller de partout à partout) en "rallongeant" de plus en plus un parcours...
Ici, les points de départ/d'arrivé doivent donc être E et B (les seuls avec un nombre impair d'arrête).
Une des solutions est : EDAECDFBCAB