Ćwiczenie numer: 4 Data oddania ćwiczenia: Temat: Cykle Eulera i Hamiltona

Cykl Eulera.

Cyklem Eulera w grafie nazywamy cykl, który przechodzi przez każdą krawędź dokładnie jeden raz (chociaż może wielokrotnie odwiedzać ten sam wierzchołek). Spójny graf skierowany ma cykl Eulera wtedy i tylko wtedy, gdy stopień wejściowy każdego wierzchołka v jest równy jego stopniowi wyjściowemu .

Przykład:

Zasada działania algorytmu.

procedure cykl_eulera(v:byte);

var

x,u,j,i:integer;

begin

for i:=1 to n do begin ce[i]:=0; stos[i]:=0; end;

i:=1;

j:=1;

stos[1]:=v;

while stos[1]<>0 do

begin

i:=1;

while stos[i]<>0 do i:=i+1;

v:=stos[i-1];

x:=za(v);

if X<>0 then

begin

u:=x;

stos[i]:=u;

tab[v,u]:=0;

tab[u,v]:=0;

v:=u;

end

else

begin

v:=stos[i-1];

stos[i-1]:=0;

ce[j]:=v;

j:=j+1;

y1:=j;

end;{od else}

end;{od while}

end;

Jako pierwszy element na stosie umieszczany jest dowolny wierzchołek z grafu ( w tym przypadku wierzchołek o numerze 1). Następnie pętla while tak długo zwiększa i aż stos[i] będzie równy zero tzn. znajdować się będzie na szczycie stosu. Później na stosie umieszczane są kolejne wierzchołki z listy ZA[v] (gdzie v jest szczytowym elementem stosu) a krawędzie są usuwane z grafu. Proces ten trwa tak długo aż lista ZA[v] będzie równa 0. Wówczas cały graf zostaje usunięty z reprezentacji, a wszystkie jego wierzchołki znajdują się na stosie. Kolejnym krokiem algorytmu jest przepisanie zawartości stosu do tablicy CE, która zawiera wynik, czyli wierzchołki ułożone w odpowiedniej kolejności , które należy aby otrzymać cykl Eulera. Złożoność tego algorytmu wynosi O(m), gdzie m jest liczbą wierzchołków. Jednak czas wykonywania jest wykładniczy, ponieważ graf o wypełnieniu np. 100% ma (n*(n-1))/2 krawędzi które algorytm musi przejść.

Cykl Hamiltona.

Cykl Hamiltona w grafie nieskierowanym G=(V,E) to cykl prosty zawierający wszystkie wierzchołki zbioru V. W cyklu tym każdy wierzchołek odwiedzany jest tylko jeden raz oraz wierzchołkiem początkowym i końcowym jest ten sam wierzchołek. W grafie może być wiele cykli ale są też grafy, które nie zawierają cykli. Problem "czy graf ma cykl Hamiltona" jest problemem NP - zupełnym co oznacza, że sprawdzenie czy dany graf ma cykl Hamiltona czy też nie jest bardzo trudne i niewykonalne w czasie wielomianowym.

Zasada działania algorytmu

procedure hamilton(k:integer);

var i,y,w :integer;

begin

if jest_ham then

repeat

y:=za(x[k-1]);

if y=0 then break;

if (k=n+1) and (y=start) then

begin

for i:=1 to n do write(x[i]);

jest_ham:=false;

end

else

if dop[y] then

begin

x[k]:=y;

dop[y]:=false;

hamilton(k+1);

dop[y]:=true;

indeks[y]:=1;

Działanie tego algorytmu można przedstawić jako proces przeszukiwania pewnego drzewa. Każdy wierzchołek drzewa odpowiada odpowiedniemu ciągowi . Rozważmy pełne drzewo D złożone ze wszystkich możliwych ciągów postaci<x1,...,xk>, gdzie 0<=k<=n i xi∈Ai dla 1<=i<=k , oraz załóżmy chwilowo, że każdy element nie jest dopuszczalny dla <x1,...xk-1>, jeśli k>n.

true jeśli k<=n

P(x1,...,xk-1,xk)=

false jesli k>n

Wywołanie dla pierwszego wierzchołka spowoduje przeszukanie w głąb całego drzewa D. W przypadku funkcji P określającej dopuszczalność wierzchołków proces przeszukiwania "opuszcza" rozpatrywanie tych wierzchołków poddrzewa o korzeniu w każdym napotkanym wierzchołku "niedopuszczalnym" (tzn. odpowiadającym ciągowi <x1,...,xk>, dla którego P (x1,..xk)=false). Na tym właśnie polega efektywność algorytmu z powracaniem w stosunku do pelnego przeglądu wszystkich możliwości.

Kod programu

program cycle;

uses dos,crt;

const m=50; {max tablicy}

krok=4;

wypelnienie=80;

b=1;{0 czytanie z pliku 1 losowanie}

type e_stos=record

poczatek,koniec:byte;

end;

var tab :array [1..m,1..m] of byte; {mac.sasiedztwa}

stos:array [1..(m*m*2)] of byte;

x:array [1..m] of byte;

ce:array [1..m*m] of byte; {stos z wierzcholkami z cyklu eulera}

indeks:array [1..m] of byte; {wektor przesuniec m.s.}

dop:array[1..m] of boolean; {czy wieszcholek odw}

y1,start,n:integer;

poczatek,koniec,wynik_h,wynik_e:real;

f,source:text;

jest_ham:boolean;

h,k3,k2,k,i,j:word;

Function WlaczTimer :LongInt;

Var Reg :Registers;

Znacznik :Byte;

Begin

Znacznik:=0;

Reg.AH:=$83;

Reg.AL:=0;

Reg.CX:=$7FFF;

Reg.DX:=$FFFF;

Reg.BX:=Ofs(Znacznik);

Reg.ES:=Seg(Znacznik);

Intr($15,Reg);

WlaczTimer:=$7FFFFFFF;

End;

Function WylaczTimer :LongInt;

Var Reg :Registers;

Begin

WylaczTimer:=MemL[$0040:$009C];

Reg.AH:=$83;

Reg.AL:=1;

Intr($15,Reg);

End;

Function CzasWykonania :Real;

Var Czas :Real;

Begin

Czas:=(Poczatek-koniec);

CzasWykonania:=Czas;

End;

procedure losuj(wyp:byte);

var temp,z,p,q:byte;

begin

if b=1 then

begin

for p:=1 to m do

for q:=p to m do

begin

z:=random(100);

if wyp >= z then

begin

temp:=random(10);

tab[p,q]:=temp;

tab[q,p]:=temp;

end

else

begin

tab[p,q]:=0;

tab[q,p]:=0;

end;

end;

for p:=1 to m do tab[p,p]:=0;

end

else

begin

assign(source,'grafh.txt');

reset(source);

readln(source,n);

for p:=1 to n do

for q:=1 to n do

read(source,tab[p,q]);

end;

end;

procedure wyswietl;

var

i,j:byte;

begin

for i:=1 to n do

begin

for j:=1 to n do write(tab[j,i]:3);

writeln;

end;

end;

function ZA(nr:integer):integer;

label 5;

var

l:integer;

begin

if indeks[nr]<>0 then {macierz sasiedztwa}

begin

if indeks[nr]<=n then

while tab[nr,indeks[nr]]=0 do

begin

indeks[nr]:=indeks[nr]+1;

if indeks[nr]>n then goto 5;

end

else goto 5;

za:=indeks[nr];

indeks[nr]:=indeks[nr]+1;

end

else

5:

begin

indeks[nr]:=0;

za:=0;

end;

end;

function sprawdz:boolean;

var i,j,licznik,licznik2:byte;

begin

licznik2:=0;

sprawdz:=true;

for i:=1 to n do

begin

licznik:=0;

for j:=1 to n do

begin

if tab[i,j]<>0 then licznik:=licznik+1;

end;

if licznik mod 2 <>0 then

begin

licznik2:=licznik2+1;

if licznik2>2 then

begin

sprawdz:=false;

break;

start:=1

end

else

start:=i;

sprawdz:=true;

end;

end;

end;

procedure cykl_eulera(v:byte);

var

x,u,j,i:integer;

begin

for i:=1 to n do begin ce[i]:=0; stos[i]:=0; end;

i:=1;

j:=1;

stos[1]:=v;

while stos[1]<>0 do

begin

{ for j:=1 to n do indeks[j]:=1;}

i:=1;

while stos[i]<>0 do i:=i+1;

v:=stos[i-1];

x:=za(v);

if X<>0 then

begin

u:=x;

stos[i]:=u;

tab[v,u]:=0;

tab[u,v]:=0;

v:=u;

end

else

begin

v:=stos[i-1];

stos[i-1]:=0;

ce[j]:=v;

j:=j+1;

y1:=j;

end;{od else}

end;{od while}

end;

procedure hamilton(k:integer);

var i,y,w :integer;

begin

if jest_ham then

repeat

y:=za(x[k-1]);

if y=0 then break;

if (k=n+1) and (y=start) then

begin

{ for i:=1 to n do write(x[i]);}

jest_ham:=false;

end

else

if dop[y] then

begin

x[k]:=y;

dop[y]:=false;

hamilton(k+1);

dop[y]:=true;

indeks[y]:=1;

end;

until false;

end;

procedure start_ham;

var i:byte;

begin

for i:=1 to n do dop[i]:=true;

x[1]:=start;

dop[start]:=false;

hamilton(2);

end

{*******************}

{ Program glowny }

{*******************}

begin

randomize;

clrscr;

Assign(f,'c:\niekaso.wac\moje\algorytm\cykle\cykle2.txt');

rewrite(f);

poczatek:= WlaczTimer;

koniec:=wylaczTimer;

n:=krok;

k3:=0;

k:=1;

wynik_e:=0;

wynik_h:=0;

repeat

wynik_h:=0;

start:=1;

for h:=1 to 100 do

begin

losuj(wypelnienie);

for j:=1 to n do indeks[j]:=1;

jest_ham:=true;

poczatek:= WlaczTimer;

start_ham;

koniec:=wylaczTimer;

wynik_h:=wynik_h+czaswykonania;

end;

writeln;

writeln('Cykl Hamiltona dla ',n,' wierzcholkow czas wyk (suma 100 pomiarow): ',wynik_h/1000000:8:5);

wynik_e:=0;

for h:=1 to 100 do

begin

start:=1;

losuj(wypelnienie);

sprawdz;

for j:=1 to n do indeks[j]:=1;

poczatek:= WlaczTimer;

cykl_eulera(start);

koniec:=wylaczTimer;

{ if sprawdz then for i:=1 to y1-1 do write(ce[i]:3);}

wynik_e:=wynik_e+czaswykonania;

end;

writeln;

writeln('Cykl eulera dla ',n,' wierzcholkow czas wyk (suma 100 pomiarow): ',wynik_e/1000000:8:5);

writeln(f,n:10,wynik_e:20:0,wynik_h:20:0);

n:=n+krok;

{if k3 mod 100 =0 then

begin

if (k=1)and(k2=1) then begin gotoxy(75,1); write('|'); k:=2; k2:=0; end;

if (k=2)and(k2=1) then begin gotoxy(75,1); write('/'); k:=3; k2:=0; end;

if (k=3)and(k2=1) then begin gotoxy(75,1); write('-'); k:=4; k2:=0; end;

if (k=4)and(k2=1) then begin gotoxy(75,1); write('|'); k:=5; k2:=0; end;

if (k=5)and(k2=1) then begin gotoxy(75,1); write('\'); k:=1; k2:=0; end;

k2:=1;

end;

k3:=k3+1;

end;}

until m<n;

close(f);

writeln('********KONIEC********');

sound(1000);

delay(100);

nosound;

end.

Tabela pomiarów i wykresy

wypełnienie 70%
liczba wierzchołków	cykl Eulera		cykl Hamiltona
[-]	[s]		[s]
5	0.10150		0.10346
10	0.10541		0.12493
15	0.12981		1.95688
20	0.16104		1.03651
25	0.25669		0.14347
30	0.42261		0.27426
35	0.67539		0.49190
40	1.08238		0.19130
45	1.65432		0.26938
50	2.45757		0.42554
wypełnienie 80%
liczba wierzchołków	cykl Eulera		cykl Hamiltona
[-]	[s]		[s]
5	0.10150		0.10053
10	0.10834		0.11419
15	0.13274		0.11810
20	0.19130		0.16494
25	0.30354		0.13762
30	0.50264		0.16006
35	0.85010		0.14347
40	1.37226		0.17080
45	2.12378		0.18934
50	3.13882		0.21277
wypełnienie 100%
liczba wierzchołków	cykl Eulera		cykl Hamiltona
[-]	[s]		[s]
5	0.10053		0.10053
10	0.11517		0.10931
15	0.13371		0.11029
20	0.24107		0.11712
25	0.40211		0.12200
30	0.71248		0.12200
35	1.21512		0.14933
40	2.00958		0.16397
45	3.13003		0.19520
50	4.69261		0.20886

Wnioski.

Ze względu na niedokładność pomiaru czasu za pomocą funkcji, której używałem zdecydowałem, że czasy podane w tabeli i na wykresach są czasami sumarycznymi 100 kolejnych pomiarów .Równocześnie taka forma pomiarów jest uśrednieniem pomiarów i eliminuje nietypowe dane wejściowe grafu .

Jak można zaobserwować na wykresach zachowanie się obu algorytmów znacznie się od siebie różni. Algorytm wyznaczający cykl Eulera jest algorytmem bardzo stabilnym, i wraz ze wzrostem wypełnienia grafu rośnie czas wyznaczenia cyklu, co się ściśle wiąże z liczbą krawędzi w grafie. Jednak jego charakterystyka jest wykładnicza co jest spowodowane tym, że liczba krawędzi jest równa w przybliżeniu (n*n)/2 . Wydawałoby się, że algorytm ten powinien mieć złożoność rzędu n ale w rzeczywistości musi on sprawdzić i przejść (n*n)/2 krawędzi. Algorytm ten jest bardzo stabilny i kształt charakterystyki czasowej jest zawsze taki sam nie zależnie od wypełnienia co jest niewątpliwie dużym plusem tego algorytmu.

Przeciwieństwem stabilności jaką prezentuje algorytm cyklu Eulera jest algorytm cyklu Hamiltona. Spowodowane jest to tym, że algorytm ten jest algorytmem klasy NP - zupełnej. Przy prawidłowej konfiguracji grafu czyli takiego, który zawiera cykl algorytm ten jest bardzo szybki, ponieważ buduje sobie drzewo, które przeszukuje odznaczając sobie drogi, w których na pewno nie ma cyklu. Taka metoda jest bardzo efektywna i nie wymaga n! porównań jak w przypadku poszukiwania rozwiązania metodą porównywania wszystkich kombinacji wierzchołków.

Z wykresów można zaobserwować, że dla wypełnienia 100% algorytm wyszukujący cykl Hamiltona jest bardzo stabilny i znacznie szybszy od algorytmu wyszukującego cykl Eulera. Jednak wraz ze spadkiem wypełnienia algorytm Hamiltona zachowuje się coraz mniej stabilnie co bardzo wyraźnie widać przy wypełnieniu 70%. Przy wypełnieniu 50%, którego wykresu nie zamieściłem w tym sprawozdaniu czas poszukiwania cyklu w niektórych przypadkach sprawiał wrażenie takiego jakby dążyłby do nieskończoności co potwierdza tezę, że sprawdzenie czy dany graf posiada cykl Hamiltona jest problemem NP - zupełnym. Nasuwa się z tego praktyczny wniosek taki, że przy rzadkim wypełnieniu grafu znalezienie w nim cyklu Hamiltona może być bardzo złożone obliczeniowo lub niewykonalne chyba, że przeprowadzimy bardzo dużo losowań grafu.

Praktyczne zastosowanie cyklu Hamiltona

Cykl ten może być wykorzystywany jako algorytm wyszukujący drogę przebiegającą przez wszystkie miasta , które są odwiedzane tylko jeden raz lub też w sieciach komputerowych do budowania sieci typu BNC, gdzie połączenie pomiędzy komputerami tworzy prawie cykl. Jednocześnie mając do dyspozycji bardzo rozbudowaną strukturę okablowania tworzącą graf.

Praktyczne zastosowanie cyklu Eulera.

Cykl ten może mieć zastosowanie wszędzie tam, gdzie wymagane jest w grafie odwiedzenie wszystkich krawędzi ale każdą z nich odwiedzamy tylko jeden raz niezależnie od ile razy odwiedzany był każdy wierzchołek

1

10

---