Graphes eulériens
Exemple 2
Les sommets de ce graphe sont de degré pair donc il y a un cycleeulérien.
1. à partir de A on forme un cycle µ (c'est toujours possible)
µ = ABCGEA , on marque les arêtes utilisées
2. On sélecte un point de µ dont il y a encore des arêtes non encore utilisées, par exp B
µ = A(B)CGEA et formons donc un cycle C1 à partir de B
C1 = BGFEDB
3. On "insère" maintenant C1 à µ en B:
µ = A(BGFEDB)CGEA
On recommence avec µ = ABGFEDBCGEA . On peut explorer en C
C2=CDAC puis on insère C2 à µ en C
µ = ABGFEDB(C)GEA
µ = ABGFEDB(CDAC)GEA
Il n'y a plus arêtes à explorer, on s'arrête
et le cycle eulérien en A est
µ = ABGFEDBCDACGEA
1 2 3 [4]
Accueil
DMJ: 23/01/2016