0000067

Gro! Hertza H(C) Joat przedstawiony na ryo.8.4.

5

Rya.8.4

TWIERDZENIE 8.12

Graf Hertza H(G) dowolnego grafu lub hlpergrafu G

nie zowlera dróg cyklicznych.

Dowód togo twiordzonio wyniko bezpośrednio z doflnlcjl okłodowoj silnoj opójności i dofinicjl grafu Hertza.

W n 1 o e e k i Każdy graf Hortzo nożna przedatowić w układzie warstwowy*. Na przykłod graf Hertza zobrazowany na rys8.4. przodotowlony Joat w układzie woretwowya no rya.8.5.

/

'S,

“4

X

t

X,

i

X.

3

X

Rys.8.5

8.5. Drogi Euloro

Droga Eulera nazywany drogę zawlorajęcę wszystkie gałęzie grafu. Z dofinicji drogi wynika, że każdo go-łęź grafu srystępujo w drodze Eulera dokładnie Jedoń raz. Nie

każdy graf zawiera drogę Eulore, Nawet Joóll graf zawiera łańcuch Eulera, to może się zdarzyć, że nie zewlera drogi Eulora. Ola letnlenia drogi Eulora graf muol opelnlać Joszcze inne warunki niż te, która ujęte e« w zolożenlach twierdzenia 5.13. Worunkl to dotyczę etopnl zewnętrznych a*(x) l atopnl wewnętrznych a"(x) wierzchołków grofu. Problea letnionie drogi Eulera w dlgraflo rozotrzyga naatępujęce twierdzenie, które podane joet bez dowodu, ze względu no powezochnę Jogo znajomość 1 możllwoóć znnlozlonla dowodu w wielu pozycjach dostępnej literatury.

TWIERDZENIE 8.13

W dlgraflo letnleje droga cykliczna Eulera wtedy l tylko wtedy, gdy dla każdego wierzchołka x grafu opeł-nlona Jeet równość o*(x) ■ t”(x). Doili natomloet istnieję tylko dwa takie wierzchołki x_Q 1 y_Q. że

“ •’<^xo⁾ " ¹ 1 •~(Y©) " °*(Y₀) 1* ¹> to letnleje droga Eulara o poczętku w x_Q i końcu w y_Q. Wyznaczenie drogi Eulera, w grafie epełnlajęcyn założenie twlerdzonla 8.13, może być dokonane za pomocę zmodyfikowanego algorytmu Ho&ng Tuy (patrz rozdz.5). Modyfikacja polega na tym, że wszędzie tam, gdzie w algorytmie aówl olę o łańcuchu proe -tym lub cyklu prostym, należy pojęcia te zamienić drogę prostę 1 drogę prostę cyklicznę. W ten spooób cechowoć będziemy gałęzie tworzęce odpowiodnie, prosto drogi cykliczne, oż do ocechowania wszystkich gałęzi grafu. Drogę wyznaczany na podstawie uzyskanych cech w sposób identyczny Jak łańcuch, poczynajęc od wierzchołka poczętkowego x_Q.

Przykład 8.3

7/yznoczymy drogę Eulera w dlgraflo przedstawionym na rys.8.6. W graflo tym s*(2) - s“(2) ■ 1 oraz s"(7) - e*{7) •

■ 1. Dla wszystkich pozostałych wierzchołków s*(x) ■ c“(x). Zatem dlgraf opołnle założenia twierdzenia 8.11 1 zowlera drogę Eulera o poczętku w wierzchołku 2 1 końcu w wierzchołku 7. Gto-eujęc zmodyfikowany algorytm Hoang Tuy znajdujemy drogę prostę od 2 do 7

np. {2, c, 3. J, 6, u. 9, t. 5. 1. A, n, 7)

133