0000072

5^C Dobierojęc odpowiednie drogi Hamiltona w poszczególnych, kolojnych okładowych silnej spójności ‘zszywamy* Je za pomoc* łuków pośrednich w colę drogę Hoeiltono.

Algorytm powyZazy oparty jeot na tezla nostępujęcego, oczywistego twierdzenia.

TWIEROZENIE 8.20

Oeśll w dlgrofie C istnieje droga Hamiltona, to w kul-dej składowej eilnoj spójności tego dlgrafu istnieje co najmniej jedna droga Hamiltona stanowiąca odcinak założonej drogi Hamiltona w dlgrofie C.

Przykład 8.4

Dlgraf G przedstawiony na rys.6.3 zawiera drogi Hamiltona. Wyznaczymy Jedn* z tych dróg oaówionya algorytmem. W przykła -dzle 8.2 wyznaczono maksymalne składowe silnej spójności oraz graf Hertza H(G). Warstwy grafu H(G) przedstawia rys.8.5. Cl*g kolejnych składowych silnej spójności w drodze Hamiltona Jeot następuj*cy {*2**4’*5'*9'*l) * ^Gro1 częściowy dlgrafu G, określony zgodnie z punktem 4° algorytmu, jest przedotawlony na rysunku 8.10, gdzie łukl pośrednie między kolejnymi okładowymi silnej spójności narysowano liniami przerywanymi.

Poszuklwon* drogę Hamiltona molo być. na przykład: droga określona przez łukl przedstawione na rys.8.10 pogrubionymi liniami.

Rys.8.10

TWIEROZENIE 8.21

OsZeli graf nie jest silnie spójny, to nie zawiera cyklicznej drogi Homlltona.

142

Dowód i

Tez* twierdzenia Jeot Implikacjo oc -e*    • Wiadomo, to

Implikacja prooto 1 przeciwstawna (~£«=>~orJ oy równoważno. Zapiazmy alowonl implikację przoclwctawny»

Dotli oraf zawiera cykliczny drogę Hamiltona, to jeot ollnio spójny. Zdanie to jeot oczywlote wobec definicji oilnej opój -noóci 1 doflnlcjl drogi Hamiltona. Kończy to dowód twlordzonia.

Oczywiócle. nie katdy dlgrof silnie spójny zawiera drogę cykliczny Hamiltona, czy nawet drogę Haailtono. Na przykład dlgraf silnie spójny, przedstawiony na ryo.6.11, nie zawiero drogi Homlltona.

I'

Ryo.6.11

/

143