Grafuri euleriene

 

 

Adeseori suntem tentati sa credem simplul fapt de a traversa strazi sau poduri nu implica nici o idee deosebita. Iata insa ca exista o celebra problema de traversare in care singura idee implicata este aceea de “traversare”, problema celor sapte poduri din Königsberg. Aceasta banala si totusi foarte controversata problema a dus la aparitia si dezvoltarea teoriei grafurilor.

Problema se pune cam asa: 55983ocu92ukf9m

Orasul Königsberg era asezat pe coasta Marii Baltice, la gurile raului Pregel. Pe rau erau doua insule legate de tarmuri si intre ele de sapte poduri ca in figura 1.

 

Oamenii care cutreierau aceste insule au observat ca daca porneau de pe malul sudic al raului, nu puteau sa-si planifice plimbarea astfel incat sa traverseze fiecare pod o singura data. Se parea ca ori trebuia sa sara un pod ori sa-l traverseze de doua ori. ck983o5592ukkf

In anul 1735 Euler a descoperit ca nu mai are rost sa se incerce, propunand urmatoarea analiza a problemei, din punct de vedere matematic:

Sa consideram mai intai insula estica (fig.2.):

sunt trei poduri care duc la ea. Deoarece se pleaca de pe malul sudic, inseamna ca se pleaca din afara insulei estice. Deoarece fiecare din cele trei traversari trebuie efectuate o singura data, plimbarea trebuie sa se termine pe insula estica.

 

 

Sa consideram acum insula vestica:

sunt cinci poduri care duc pe ea, iar cinci este din nou numar impar. Asadar plimbarea incepe in afara insulei, si deci trebuie sa se termine pe insula vestica.

Aceasta inseamna ca plimbarea se termina in doua locuri diferite simultan ceea ce e imposibil.

Solutia data de Euler este tipica pentru personalitatea si ingeniozitatea sa. Tot el a scris in anul 1736 prima lucrare de teorie a grafurilor despre problema acestor sapte poduri.

Un ciclu al unui graf G care contine toate muchiile lui G se numeste ciclu eulerian. Un graf G care are un ciclu eulerian se numeste graf eulerian.

Un graf G fara varfuri izolate este eulerian daca si numai daca este conex si gradele tuturor varfurilor sale sunt numere pare.

Din punct de vedere al teoriei grafurilor, problema se pune cam asa: cele patru regiuni (insule si maluri) A,B,C,D si cele sapte poduri le reprezentam in graful urmator:

 

Muchiile grafului reprezentand posi-bilitatile de trecere de pe un mal pe un pod si reciproc.

Problema are solutie daca acest graf contine un ciclu eulerian. Un astfel de ciclu, utilizeaza la fiecare trecere printr-un varf doua muchii ce nu mai pot fi folosite pentru o noua trecere. Cum fiecare dintre cele patru varfuri (A,B,C,D) au grade impare, rezulta ca ultima muchie va ramane nefolosita sau va fi folosita pentru a face trecerea de final ( pentru a incheia plimbarea). Aceasta ar insemna ca ori va ramane la unul din varfuri, o muchie nefolosita (fapt ce demonstreaza ca nu avem un ciclu eulerian) ori plimbarea ar trebui sa se termine in mai multe locuri simultan ceea ce e iarasi imposibil.

Ciclu eulerian: Fiind dat un graf neorientat, sa se verifice daca este graf eulerian si in caz afirmativ, sa se determine un ciclu eulerian al sau.

Explicatia programului:

Pornim dintr-un varf neizolat retinut cu ajutorul variabilei prim, in cadrul procedurii de citire, apoi cautam un ciclu eulerian al grafului printr-un algoritm backtracking. Vom folosi pentru retinerea ordinii varfului in ciclul eulerian un sir s.

In cadrul procedurii de cititre a matricii de adiacenta, numaram si muchiile grafului cu ajutorul variabilei m.

Functia valid verifica daca varful k apartine ciclului eulerian (daca este adiacent cu varful anterior determinat, iar in cazul in care este ultimul varf k=m daca este adiacent cu primul vafr al ciclului).

Procedura back cauta succesiv, autoapelandu-se, varfuri adiacente cu varful anterior determinat pana cand se ajunge la ultimul varf al ciclului (k=m); in acest caz, variabila booleana gasit care a fost initializata pe false, ia valoarea true si este tiparit sirul s incheindu-l cu primul varf al sau (pentru a arata ca este un ciclu).

Daca nu a fost gasit nici un ciclu eulerian al grafului dat (gasit=false), atunci graful nu este eulerian si se tipareste mesaj.

Acelasi lucru se intampla si daca graful nu are varfuri neizolate (prim=0).

program ciclu_eulerian;

uses crt;

type mat=array [1..20,1..20] of integer;

sir=array [1..20] of integer;

var a:mat;s:sir;

n,m,i,j,k,prim:integer;

gasit:boolean;

procedure cit;

begin

write('n=');readln(n);

m:=0;prim:=0;

for i:=1 to n-1 do

for j:=i+1 to n do

begin

write('a[',i,',',j,']=');readln(a[i,j]);

if a[i,j]=1 then

begin

m:=m+1;

prim:=i;

end;

a[j,i]:=a[i,j];

end;

end;

function valid(k:integer):boolean;

var i:integer;

begin

valid:=true;

if a[s[k],s[k-1]]=0 then valid:=false;

if (k=m)and(a[s[k],s[1]]=0)then valid:=false;

end;

procedure back(k:integer);

var i,j:integer;

begin

i:=1;

while (i<=n)and(not gasit) do

begin

s[k]:=i;

if valid(k) then

begin

a[s[k],s[k-1]]:=0;

a[s[k-1],s[k]]:=0;

if k=m then

begin

gasit:=true;

writeln('Ciclul eulerian este:');

for j:=1 to m do write(s[j],' ');

writeln(s[1]);

end

else back(k+1);

a[s[k],s[k-1]]:=1;

a[s[k-1],s[k]]:=1;

end;

i:=i+1;

end;

end;

procedure tip;

begin

clrscr;

writeln('Matricea de adiacenta:');

for i:=1 to n do

begin

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

writeln;

end;

writeln;

end;

begin{PP}

clrscr;

cit;

tip;

if prim<>0 then

begin

s[1]:=prim;

gasit:=false;

back(2);

if not gasit then write('Graful nu este eulerian.');

end

else write('Graful nu este eulerian.');

readkey;

end.

In viata de zi cu zi rezolvam adesea, fara sa ne dam seama probleme de grafuri euleriene, de exemplu cand vrem sa mergem cu trenul in circuit si vrem sa platim mai putin, calculam in asa fel incat sa trecem peste tot si sa platim mai putin. Dar aceasta nu o facem numai noi si postasii, ci grafurile se utilizeaza la calcularea pozitilor optime de amplasare a satelitilor de comunicatie pentru ca informatia transmisa sa foloseasca putin timp, caci in noua era :,, time is money.

 

Scriitori romani