0000071

Załóżmy teraz. Ze każdo wora twa digrefu zoniera po Jodnym wlorz-chołku 1 w digrefle nie istnieje drogo Hamiltona. Uzyekujomy no-tychaloet sprzeczność z tezę twlerdzonla 8.11, któro kończy dowód twierdzenia.

Teza twierdzenia 8.18 rozstrzyga problem lstnlenlo dróg Hamiltona w dlgrofoch ocykllcznych 1 dostarcza jednocześnlo algorytmu dla wyznaczonlo ietniejęcoj drogi. Należy boniom wyznaczyć worstwy digrefu, a clęg wierzchołków kolejnych warstw ste-nowl drogę Hamiltona. Na przykłod drogę Hamiltona grofu z ry -eunku 8.4 stanowi clęg wiorzchołków {•2'®4'^B5*^B3^,ci} * ^c0 J^0#t pokazane no rys.8.5. Natomiast digraf z rys.8.2 nie zonlera drogi Hamiltona, ponieważ już warstwa zerowa togo dlgrafu zawlora dwa wiorzchołkl.

TWIERDZENIE 8.17    •

Dożęli w grafie C istnieje droga Hoeiltona, to ist- .

niejo odpowiednia drogo Hoeiltona n grafie Hertza

H(C) tego grafu.

O o w ó d i

Tezo twierdzenia Ject implikację, którę dowiedziemy przez zaprzeczenie.

Załóżmy, że teza jest nieprewdziwo, to znaczy letnlejo

drrga Hamiltona    (x_J.....X l i jednocześnie w grafie H(G) •

- <S ,P> (S ■ ^Sj,... ,e_K^ ) droga Homiltona nie istnieje. Weźmy dowolny wlerzchołok #_k£ S, to znaczy skłodowę silnej spójności grafu G. Z defioicji maksymalnej ekłedowoj silnej spójności wy-* nika, że wierzchołki grafu G należęce do s_k muszę w drodze tworzyć podzbiór kolejnych wierzchołków drogi. Możemy zotom clęg |x₁,...,x_n| podzielić no K rozłęcznych, kolejnych podcięgów odpowiada Jęcych poozczogólnym składowym o_k ; k ■ 1.....K. Clęg

tych okładowych tworzy drogę Hamiltona w grafie H(G), co przeczy założeniu 1 kończy dowód twierdzenie.

Teza twierdzenie 8.17 ( implikacja prosta cx —*    ) pozwa

la stwierdzić brak drogi Homiltona w digrefle G (implikacja przeciwstawna — JS -e -oC). Należy w tym celu zbudować graf H(G) i Skorzystać z twierdzenia 8.16. Dodnak w wypadku, gdy w H(G) istnieje droga Hamiltona, to nic nie możomy powiedzieć na temat istnienia drogi Hamiltona w dlgrafle G. Istnienie bowiem tej drogi zaloty od Istnienia odpowiednich, nodajęcych tlę do "zażycia”, dróg Haalltona w poszczególnych okładowych ellnoj opój -noścl.

W literaturze nożna znaleźć wiole twiordzeń dotyczących lstnlonla dróg Haalltona w digrafoch silnie spójnych. Ola przykładu wybrano dwa twierdzenia.

TWIERDZENIE 8.18

Dlgraf, będęcy połnye unlgrafea jest digrefoa silnie opójnya 1 zawiera drogę cyklicznę Haalltona.

Dowód i

Ola każdego takiego digrefu nożna utworzyć Jego dlgraf częóclowy, epołnlajęcy założenia twierdzenia 8.15 i tya saaya zawlerajęcy drogę cyk i.lcznę Haalltona.

Zatoa, tya bardziej, istnieje droga Haalltona w oaewlanya di-grafle pełnya.

TWIEROZENIE 8.19 (Choulla-Houri A.)

Worunklen dottatecznya dla latnlenlo cyklicznej drogi Haniltona w dlgrafio 8ergo*a silnie epójnya, bez pętli C • <X,P> jaet. oby

A (ir(x)Mr~^&(«)|) > n , ⁿ ■ |X|

xEX

Dowód togo twlardzenia nożna znaleźć w [53].

Przejdżny teraz do problonu wyznaczenia drogi Haniltona w dowolny* digrafie G przy założeniu letnlanla tej drogi.

Drogę tę nożna wyznaczyć za poaocę następującego algo -

rytau t

1° Wyznaczany wszystkie składowe silnej spójności dlgrafu G.

2° Tworzyay graf Hertza H(G).

3° Wyznoczoey warstwy grafu Hertza, a tya eoaya clęg kolej -

nych składowych ollnej spójności {sj.....o_KJ , tworzęcych

drogę Haalltona w grafie Hertza, a Tworzyay graf częściowy dlgrafu G w ten eposób, że pozooto-wloay łuki należęce do składowych silnej spójności oroz łu-kl (pośrodnlo) łęczęce sęnlodnle składowe silnej spójności w cięgu Je^.....s_KJ.

141