2500335698

9 Metoda cyklu Eulera Niech G — (V", E) spójny graf prosty. Możemy utworzyć graf G' o tym samym zbiorze wierzchołków V oraz zbiorze krawędzi E' otrzymanym przez zastąpienie każdej nieskierowanej krawędzi E 3 e = {u, u} poprzez dwie krawędzie skierowane (u,v) i (v,u). Fakt 2 Otrzymany w ten sposób graf jest Eulerowski.		Notatki
Rozważmy teraz drzewo T. Zaczniemy od znalezienia cyklu Eulera w V = (V, E'). Niech v € V będzie wierzchołkiem w T, a N(v) = {u0i U\,U2,..., «deg(u)-i} listą sąsiadów. Istotne jest, że dla każdego wierzchołka v zbiór sąsiadów N(v) musi być uporządkowany. Dla każdej krawędzi (ui,v) definiujemy następnik SUCc(Ui,v) = (v,Ui+ l(mod deg(t>))) Fakt 3 Tak zdefiniowana funkcja suce - (następnik) definiuje cykl Eulera w V.		Notatki

15