W każdej iteracji algoryt przechodzi jak¸aś kraw¸edź. Albo wkładaj¸ac jej koniec na STOS, albo przekładaj¸ac j¸a na wyjście CE. A ponieważ każda kraw¸edź jest odwiedzana dokładnie dwa razy, raz jak jest wkładana na STOS i drugi raz jak jest przekładana na CE, wi¸ec czas działania algorytmu jest proporcjonalny do liczby kraw¸edzi w grafie.
1.10
Drogi i cykle Hamiltona Droga Hamiltona to taka droga w grafie, która przechodzi dokładnie raz przez każdy wierzchołek grafu. Cykl Hamiltona to zamkni¸eta droga Hamiltona.






Przykład 1.36 Graf z rysunku 1.1 posiada drog¸e Hamiltona
3
2
4
, ale nie po-
5
/
*
6
siada cyklu Hamiltona. Każdy graf pełny
z
posiada cykl Hamiltona.




22
Rozdział 1. Grafy (nieskierowane)
Inaczej niż dla cyklu lub drogi Eulera nie jest znane żadne proste kryterium rozstrzy-gania, czy dany graf posiada drog¸e lub cykl Hamiltona. Nie jest także znany żaden algorytm wyszukiwania drogi lub cyklu Hamiltona działaj¸acy w czasie wielomianowym.
Naiwnym sposobem szukania drogi Hamiltona jest sprawdzanie wszystkich możliwych dróg w grafie, ale algorytm ten jest bardzo czasochłonny, bo mamy około
możliwych

dróg w grafie z
wierzchołkami.

Innym algorytmem szukania drogi Hamiltona jest tak zwane wyszukiwanie z nawrotami. Mówi¸ac w skrócie szukanie z nawrotami idzie pierwsz¸a możliw¸a ścieżk¸a tak daleko jak to tylko możliwe okładaj¸ac kolejne odwiedzane w¸ezły na stos. W momencie, gdy al-gorytrm utknie w ślepej uliczce, to cofa si¸e o jeden krok i próbuje innej drogi. Załóżmy, że wierzchołki grafu s¸a uporz¸adkowane na przykład według alfabetu lub s¸a kolejnymi

=
- (?((@

liczbami naturalnymi

Algorytm z nawrotami wyszukiwania drogi Hamiltona

.

"
Dane wejściowe: graf
oraz wierzchołek pocz¸atkowy
.

Dane wyjściowe: droga Hamiltona zaczynaj¸aca si¸e od , lub informacja, że takiej drogi nie ma.


włóż
na STOS

powtarzaj aż do skutku:

jeżeli
jest wierzchołkiem na wierzchu STOSU, to szukamy wierzchołka
%

o najniższym możliwie numerze poł¸aczonego z
kraw¸edzi¸a i nie wyst¸epuj¸acy
%
na STOSIE. Jeżeli w poprzedniej iteracji zdj¸eto ze STOSU wierzchołek
, to

powinien być wi¸ekszy od .

%
Jeżeli takie
znajdziemy, to wkładamy je na STOS. Jeżeli wierzchołki na
STOSIE tworz¸a już drog¸e Hamiltona, to koniec algorytmu.
%

Jeżeli takiego
nie znajdziemy, to zdejmujemy
ze STOSU.
Przykład 1.37 Prześledźmy działanie algorytmu na przykładzie grafu z rysunku 1.1. Po-niższa tabela zawiera: odwiedzany wierzchołek, oraz stan STOSU po każdym kolejnym kroku (szukanie rozpoczynamy od wierzchołka ).
/
1.11. Kolorowanie grafów
23
Krok
wierzchołek
STOS
1
d
d
2
a
da
3
b
dab
4
c
dabc
5
f
dabcf
6
e
dabcfe
7
f
dabcf
8
g
dabcfg
9
f
dabcf
10
c
dabc
11
g
dabcg
12
f
dabcgf
13
e
dacgfe
Powyższy algorytm mimo, że szybszy od naiwnego algorytmu sprawdzania wszystkich dróg, ma wykładnicz¸a złożoność czasow¸a.
1.11 Kolorowanie grafów
Chodzi o takie pokolorowanie wierzchołków grafu, żeby wierzchołki poł¸aczone kraw¸edzi¸a były pokolorowane innymi kolorami i żeby liczba kolorów była jak najmniejsza.






Definicja 1.38 Pokolorowanie grafu
kolorami jest to funkcja 4


-> ?((?(@

0
;%

01
,- .#


, taka że 4
4
jeżeli
.
Najmniejsze takie
, że graf
można pokolorować
kolorami nazywamy liczb¸a


chromatyczn¸a grafu
i oznaczamy przez
.
W przypadku kolorowania grafów, podobnie jak dla dróg Hamiltona, nie s¸a znane dobre i szybkie algorytmy. Naiwny algorytm sprawdzaj¸acy wszystkie możliwe kolorowania działa zbyt długo. Także tu mamy algorytm z nawrotami.
Algorytm z nawrotami kolorowania wierzchołków grafu
== .

Dane wejściowe: graf
oraz liczba naturalna .


Dane wyjściowe: pokolorowanie wierzchołków grafu
za pomoc¸a
kolorów 4

-> ?((?(@

lub informacja, że takiego pokolorowania nie ma.



01


0





dla każdego
podstaw 4
(4
oznacza, że
nie ma jeszcze

koloru).

włóż pierwszy wierzchołek na STOS,

powtarzaj aż do skutku:

jeżeli
jest wierzchołkiem na wierzchu STOSU, to próbujemy przypisa ć mu
0

kolor, wi¸ekszy od bież¸acego koloru 4
, który nie koliduje z kolorami wierzchoł-