Bonjour,
dans le cas d'un graphe connexe dont tous les sommets sont de degré pair, nous savons d'après le théorème d'Euler qu'il existe un cycle eulérien.
Mais comment pouvons-nous savoir de quel sommet X il faut partir pour revenir au même sommet X en ne passant qu'une et une seule fois par toutes les arêtes ?
Merci beaucoup !
C.
cycle eulérien
-
Cédric
-
sos-math(21)
- Messages : 10354
- Enregistré le : lun. 30 août 2010 11:15
Re: cycle eulérien
Bonjour,
le point de départ n'a pas d'importance et la procédure algorithmique est la suivante :
1. Déterminer un cycle \(C\) quelconque.
2. Si \(C\) couvre toutes les arêtes du graphe alors STOP, sinon aller à 3.
3. Choisir un sommet \(v\) dans \(C\) qui est l’extrémité d’une arête hors de \(C\). Construire un deuxième cycle \(C’\) contenant \(v\) et tel que \(C\) et \(C’\) n’aient aucune arête en commun.
4. Fusionner \(C\) et \(C’\) pour former un cycle \(C’’\). Cette fusion se fait en partant du sommet \(v\), en parcourant l’ensemble du cycle \(C\) puis étant revenu au sommet \(v\) en visitant l’ensemble du cycle \(C’\) pour finalement terminer en \(v\).
5.Poser \(C\) égal à \(C’’\) et retourner en 2.
Pour plus de précision, tu peux consulter le cours http://www.gymomath.ch/javmath/polycopie/th_graphe6.pdf (page 3 section 6.2)
Bonne application
le point de départ n'a pas d'importance et la procédure algorithmique est la suivante :
1. Déterminer un cycle \(C\) quelconque.
2. Si \(C\) couvre toutes les arêtes du graphe alors STOP, sinon aller à 3.
3. Choisir un sommet \(v\) dans \(C\) qui est l’extrémité d’une arête hors de \(C\). Construire un deuxième cycle \(C’\) contenant \(v\) et tel que \(C\) et \(C’\) n’aient aucune arête en commun.
4. Fusionner \(C\) et \(C’\) pour former un cycle \(C’’\). Cette fusion se fait en partant du sommet \(v\), en parcourant l’ensemble du cycle \(C\) puis étant revenu au sommet \(v\) en visitant l’ensemble du cycle \(C’\) pour finalement terminer en \(v\).
5.Poser \(C\) égal à \(C’’\) et retourner en 2.
Pour plus de précision, tu peux consulter le cours http://www.gymomath.ch/javmath/polycopie/th_graphe6.pdf (page 3 section 6.2)
Bonne application
-
Cédric
Re: cycle eulérien
Merci beaucoup !
C.
C.