0000070

w ton opocób zbiór wierzchołków X zoatoł podzielony no dno podzbiory: X_£ - podzbiór wierzchołków nalolęcych do drogi cykllcz-

cych do drogi ^u_c.

Wykażemy, ±o Jeżeli do X_£ rilo nnleżo wazyotkle wierzchołki grafu, to drogę cykliczne ₍u_£ aotna wydłużyć za poaoce po-zootołych wierzchołków tak. aby droga Vydlużona pozostała drogę cykliczne prootf. Podzielmy w tye celu zbiór wierzchołków X \X_c na trzy podzbiory:

X* - do którogo należe takie wierzchołki, że łukl łeczece je

z wierzchołkami zbioru X_£ oo skierowane do zbioru X_£ ;

X^- - do którogo nalażf takie wierzchołki, że łukl łeczece je

z wlerzchołkaal zbioru X„ sf skierowane od zbioru X„ do

c    c

x“.

X° - do którego nałożę wierzchołki poleczone z wierzchołkami X łukaal o różnych kierunkach.

v<ozay dowolny wlerzcnołek xCX°. Oesc on poleczony odpo -wlodnimi łukaal ze wszystkimi wierzcnołkami zbioru X_c> Mual zetem istnioć taka para kolejnych wierzchołków ^*_r.*_r4l> drogi ^i_c. że istnieje łuki <*,.*> i    • Wtedy drogę <u_c

przedłużony do drogi cyklicznej, prostej ^u'_c • {x_fc.....

x.x ,,....x ,x. } . A ton sposób nożns sukceoywnio wyczerpać

•♦1    n K J    ę    ^

wszystkie wierzchołki zDloru X 1 zostanę jedynie zbiory X 1 X" ’(patrz rys.8.9).

Rys.8.9

Zauważmy, żo muszy lotnioć łukl prowodzęca zo zoioru X“ do zbioru X⁴ oraz oba ta zbiory auozy być nlepuste o lla jedon z nich Joot nlepuety. W przeciwny* bowiem wypodku istniałyby wbrow założeniu zamknięta zbiory wierzchołków.

Wybierzmy dwa wiorzchołkl x⁴C X⁴ i x“€ X" tokle, żo istnieje łuk<x",x⁴> . Każdy z tych wiorzchołków jaat połyczony odpowiednimi łukami ze wozyotklni wierzchołkami zbioru X_£. Zatem dowolna paro kolejnych wierzchołków <^xr*^xr+i> drogi ^u_c apałnlo worunek polegajycy na tym, ża ietnlejy łukl <x_r,x”> oraz ^x⁴,x_rłl^ . Można zatem wydłużyć drogę ^u_c do drogi cyklicznej prootej ju'_c • {x_k,... ,x_r,x", x⁴,x_p4ł,... *^xn*^xk} •

W ten apooób można sukcesywnie wyczerpać wszystkie wierzchołki zbiorów X⁴, X~ i uzyskoć w wyniku drogę cykliczny Hamiltona. Kończy to dowód twierdzenia 8.15.

Zauważmy, że dowody twierdzeń 8.14 1 8.15 zowierojy kon-etrukcje będyce algorytmami wyznaczania omawianych dróg Hamiltona w przeciwoyoetrycznych grafach Oorgo'a, opełnlojycych zo-łożonla tych twierdzeń.

Orogę Hamiltona w dowolnym grafie okierowanya (o llo iot-nlejo) możno wyznoczyć konstruujyc grat Hertza tego grafu i ko-rzyotajyc z pojęcia warotw dlgrafu acyklicznego. Mówię o tym twiordzenlo 8.16 i 8.17.

TWIERDZENIE 8.16

W dlgrafle acyklicznym w aenoie dróg istnloje drogo Hamiltona wtody 1 tylko wtody, gdy każdo warstwa togo dlgrafu zawiera po jednym wierzchołku.

Dowód t

Równoważność w tozlc twiordzenlo można traktować jako konlunkcję dwóch implikacji - prostej 1 odwrotnej, które nałoży dowioóć.

Załóżmy, żo jost nieprawdziwa implikacja prosta, to znaczy w digroflo istnieje drogo Hamiltona 1 istnieje warstwo X_k tego dlgrafu zawlerajyce więcej nil jeden wierzchołek. Pierwszy wierzchołek z warstwy X_k wyotępujycy w drodzo Hamiltona oznoczyny przez x_kl, a następny przez x_k2» Z twierdzeń 8.9, 8.10 i 8.11 wyniko, że nio iotnleje w digroflo droga _<^u(^xj_cl»^xj_c2)' ^kt6ro etanowi odcinek założonej drogi Homiltona. Uzyskano sprzeczność kończy dowód implikacji prostej.

139