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.
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;
738
659
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.
