Uzdevums: Dots sakarīgs grafs, programma atrod un uzrāda vismaz vienu Eilera ciklu.
Risinājums: Programma veidota Pascal valodā, programma “Turbo Pascal 7.0”. Datu ievade un izvade notiek failos (atbilstoši “Eiler.in” un “Eiler.out”). Grafs tiek uzdots ar savu virsotņu blakus attiecības sarakstu struktūru Adj[x], kur Adj[x] – virsotņu daudzums, kas saistītas ar x piederošo X. Rezultējošā Eilera ķēde formējas daudzumā Z.
Algoritms šī uzdevuma veikšanai:
v c X; {Eilera cikla sākuma virsotne}
Z = {v}; {veidojamās Eilera ķēdes sākums}
R = O; {Eilera ķēdes paplašinošais cikls}
repeat
Cycle(v,R);
Z = Z U R; {ciklu apvienošana vienā ciklā}
until Not v c Z |Adj[v]|>0
procedure Cycle(v,R)
R = {v}; {Eilera ķēdes atsevišķa cikla veidošana}
repeat
w = Adj[v];
R = R U {w}; {nodzēst noieto šķautni (v,w) }
if v=w then Adj[w]=Adj[w]{v}; {nodzēst šķautni (v,w)}
v = w;
until Not |Adj[v]|>0; {kamēr nav noietas visas šķautnes}
end;
Piemērs: dotais grafs attēlots zīmējumā:
7 3 8
2 1 4
6 5 9
Ieejas datu struktūra tiek uzdota ar teksta failu „Eiler.in”. Pirmais skaitlis norāda virsotņu skaitu, tālāk katrā rindā pirmais cipars norāda virsotni, ar to saistīto virsotņu skaitu, tad šo virsotņu sarakstu:
9
1 4 2 3 4 5
2 4 1 3 6 7
3 4 1 2 7 8
4 4 1 5 8 9
5 4 1 4 6 9
6 2 2 5
7 2 2 3
8 2 3 4
9 2 4 5
Izskaitļojumu rezultāti tiek saglabāti izejas teksta failā „Eiler.out” ar sekojošu struktūru:
Z= 1
R= 1 2 3 1 4 5 1
Z= 1 2 3 1 4 5 1
R= 5 6 2 7 3 8 4 9 5
Z= 1 2 3 1 4 5 6 2 7 3 8 4 9 5 1
O= 1 2 3 1 4 5 6 2 7 3 8 4 9 5 1
Katrā solī tiek parādīta veidojošās Eilera ķēde Z, kas tiek paplašināta ar R izdalīto ciklu. Rezultējošais Eilera cikls tiek atzīmēts ar O rindas sākumā.
Programmas kods:
program EilerWay;
uses CRT,DOS;
const
nVertex=100; {maksimālais virsotņu skaits}
nAdjacent=1000; {maksimālais blakusattiecības saraksta garums}
Type
TypeVertex=array[1..nVertex] of Integer;
TypeAdjacent=array[1..nAdjacent] of Integer;
Var
f:Text; {teksta fails}
ks:Integer; {Eilera cikla sākuma virsotne}
n:Integer; {virsotņu skaits}
Adj:TypeAdjacent; {grafa virsotņu blakusattiecības saraksts}
Fst:TypeVertex; {blakusattiecību saraksta virsotņu rādītāji}
Nbr:TypeVertex; {virsotņu skaits blakusattiecības sarakstā}
Vtx:TypeVertex; {grafa virsotņu saraksts}
Deg:TypeVertex; {grafa virsotņu pakāpes}
kz:Integer; {virsotņu daudzums Eilera ciklā}
z:TypeAdjacent; {virsotņu secīgums Eilera ciklā}
r:TypeAdjacent; {atsevišķais paplašinošais cikls}
Procedure Init(Var yes:Boolean);
var
i,j,k,m:Integer;
begin
{Nolūks ir atzīmēs virsotnes ar to kārtas numuriem blakusattiecības sarakstā}
{yes – blakusattiecības saraksta pareizas struktūras signāls}
for i:=1 to n do
for j:=1 to Nbr[i] do begin
yes:=FALSE;
for m:=1 to n do
if Adj[Fst[i]+j]=Vtx[m] then begin
yes:=TRUE;
Adj[Fst[i]+j]:=m;
break;
end;
if not yes then exit;
end;
{izvietot cilpas blakusattiecības saraksta sākumā}
for i:=1 to n do begin
k:=1;
for j:=1 to Nbr[i] do
if Adj[Fst[i]+j]=i then begin
Adj[Fst[i]+j]:=Adj[Fst[i]+k];
Adj[Fst[i]+k]:=i;
k:=k+1;
end;
end;
{grafa virsotņu pakāpes}
for i:=1 to n do begin
Deg[i]:=0;
for j:=1 to Nbr[i] do begin
Deg[i]:=Deg[i]+1;
if Adj[Fst[i]+j]=i then Deg[i]:=Deg[i]+1; {cilpa}
end;
end;
{ks cikla sākuma virsotnes meklēšana}
k:=0; ks:=1;
for i:=1 to n do if (Deg[i] mod 2)>0 then begin
k:=k+1;
ks:=i;
end;
if (k<>2) and (k<>0) then yes:=FALSE; {grafs nav Eilera}
end;
Procedure Cycle(v:Integer; varcount:Integer);
{atsevišķā Eilera cikla r[] veidošana}
var
w:Integer;
i,j,count:Integer;
begin
count:=1;
r[count]:=v;
repeat
w:=Adj[Fst[v]+1]; {nākošā ķēdes virsotne}
count:=count+1;
r[count]:=w;
{nodzēst šķautni (v,w) no blakusattiecību saraksta virsotnei v}
Fst[v]:=Fst[v]+1;
Nbr[v]:=Nbr[v]-1;
{ja šķautne (w,v) nav cilpa, tad nodzēst arī to no saraksta virsotnei w}
if v<>w then
for i:=1 to Nbr[w] do if Adj[Fst[w]+i]=v then begin
for j:=i+1 to Nbr[w] do
Adj[Fst[w]+j-1]:=Adj[Fst[w]+j];
Nbr[w]:=Nbr[w]-1;
break;
end;
v:=w;
until Not(Nbr[v]>0);
end;
Procedure Eiler;
var
v,w:Integer;
i,j,kt:Integer;
count:Integer;
yes:Boolean;
begin
v:=ks; kz:=1;
kt:=kz; z[kz]:=v;
Write(f,’Z=’); {līdz apvienošanai}
for i:=1 to kz do Write(f,Vtx[z[i]]:3);
Writeln(f);
repeat
Cycle(v,count);
Write(f,’R=’);
for i:=1 to count do Write(f,Vtx[r[i]]:3);
Writeln(f);
for i:=1 to count-1 do begin
z[kz+i]:=z[kt+i];
z[kt+i]:=r[i+1];
end;
kz:=kz+count-1;
Write(f,’Z=’); {pēc apvienošanas}
for i:=1 to kz do Write(f,Vtx[z[i]]:3);
Writeln(f);
yes:=FALSE;
for i:=kz downto 1 do if Nbr[z[i]]>0 then begin
v:=z[i];
kt:=i;
yes:=TRUE;
break;
end;
until Not yes;
end;
var
i,j:Integer;
yes:Boolean;
begin
Assign(f,’Eiler.in’);
Reset(f); {fails atvērts nolasīšanai}
{blakusattiecības saraksta ievade}
Read(f,n); {rindu daudzums sarakstā}
Fst[1]:=0; {rādītājs uz saraksta pirmās rindas sākumu}
for i:=1 to n do begin
Read(f,Vtx[i]); {virsotnes atzīmēšana}
Read(f,Nbr[i]); {virsotņu daudzums sarakstā}
for j:=1 to Nbr[i] do Read(f,Adj[Fst[i]+j]);
{saistīto virsotņu saraksts}
Fst[i+1]:=Fst[i]+Nbr[i]; {rādītājs uz saraksta nākošās rindas sākumu}
end;
Close(f);
Assign(f,’Eiler.out’);
Rewrite(f); {fails atvērts pārrakstīšanai}
Init(yes);
if not yes then begin
Writeln(f,’Nepareiza grafa struktura’);
Writeln(f,’vai rgafs nav Eilera’);
Close(f);
exit;
end;
Eiler;
Write(f,’O=’);
for i:=1 to kz do Write(f,Vtx[z[i]]:3);
Writeln(f);
Close(f);
end.