Graphes eulériens
Exemple 1
Le graphe a 2 sommets de degré impair A et D donc il y a une chaine eulérienne entre A et D.
1. à partir de A on forme une chaine µ entre A,D (c'est toujours possible)
µ = ABCED , 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 D
µ = ABCE(D) et formons donc un cycle C1 à partir de D
C1 = DBFD
3. On "insère" maintenant C1 à µ en D:
C1 = DBFD
µ = ABCE(D)
µ=ABCE(DBFD)
On recommence avec µ=ABCEDBFD. On peut explorer en F
C2=FGAF puis on insère C2 à µ en F
µ=ABCEDB(F)D
µ=ABCEDB(FGAF)D
On peut explorer en G
C3=GIJKIHG
On insère C3 à µ en G
µ=ABCEDBF(G)AFD
µ=ABCEDBF(GIJKIHG)AFD
On explore K
C4=KHAK
on insère C4 à µ en K
µ=ABCEDBFGIJ(K)IHGAFD
µ=ABCEDBFGIJ(KHAK)IHGAFD
Il n'y a plus arêtes à explorer, on s'arrête
et la chaine eulérienne entre A et D est
µ=ABCEDBFGIJKHAKIHGAFD
1 2 [3] 4
Accueil
DMJ: 23/01/2016