MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

ATESTAT PROFESIONAL

Prof.Îndrumător:Săceanu Ion

Elev:Vâlsan Alina CorinaProfil:Matematica-Informatică

Colegiul Tehnic Mătăsari

2015

1

MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

DRUMURI ÎN GRAFURI ORIENTATE

Prof.Îndrumător:Săceanu Ion

Elev:Vâlsan Alina CorinaProfil:Matematica-Informatică

Colegiul Tehnic Mătăsari

2

2015

CUPRINS

Grafuri orientate ............................................................................4Drumuri minime și maxime în grafuri orientate................................5 Altgoritmul lui Dijkstra.................................................................8

Altgoritmul lui Roy-Floid...............................................................12Drumuri maxime în grafuri orientate..............................................16

Grafuri euleriene..........................................................................19 Grafuri hamiltoniene..............................................................24

Bibliografie...................................................................................26

3

Grafuri orientateNoțiuni de bază

Un graf orientat G este format dintr-o pereche ordonată de mulţimi G= (X, U). ca şi în cazul grafurilor neorientate, X este mulţimea vârfurilor sau nodurilor grafului. Mulţimea U este formată din perechi ordonate de elemente distincte din X, numite arce. Orice arc u U va fi notat prin u= (x, y) cu x, yX şi xy.

Spunem că vârful x este extremitatea iniţială a arcului u, iar vârful y este extremitatea finală a arcului u. Spre deosebire de cazul grafurilor neorientate, notaţiile (x, y) şi (y, x) vor desemna doua arce diferite.

Dacă graful G conţine arcul (x, y) vom spune că vârfurile x şi y sunt adiacente în G şi amândouă sunt incidente cu arcul (x, y). Deci, un graf orientat G poate fi imaginat că o mulţime de vârfuri, dintre care unele sunt unite două câte două prin arce. Un graf orientat poate fi desenat în plan reprezentând vârfurile sale prin puncte şi arcele prin săgeţi care sunt orientate de la extremitatea iniţială către extremitatea finală a fiecărui arc.

Graful orientat G= (X, U) unde: X= {1,2,..., 8} şi U= {(1,2), (2,3), (3,1), (3,2), (2,4), (4,5), (3,5), (6,8), (8,7), (7,8), (7,6)} se reprezintă ca în figură:

4

2 u5 4

u1

1 u3 u4 u7

u2

3 u6 5

Vom nota arcele așa cum se indică în figură , adică u1=(1,2), u2=(3,1),…., u11=(6,8).

Gradul exterior al unui vârf x, notat prin d+(x), este numărul arcelor de formă (x,y) cu yX. Gradul exterior al unui vârf x, notat prin d-(x),este numărul arcelor de formă (y,x) cu yX.

Un graf parţial al unui graf orientat G=(X,U) se defineşte în acelaşi mod ca şi în cazul neorientat. El este un graf G1=(X,V) unde VU, deci este graful G însuşi sau se obţine din G prin suprimarea anumitor arce.

Şi definiţia unui subgraf al unui graf orientat G=(X,U) este asemănătoare cu cazul neorientat.Prin definiţie , un subgraf al lui G este un graf H=(Y,V), unde YX, iar arcele din V sunt toate arcele din U care au ambele extremităţi în mulţimea de vârfuri Y. Deci un subgraf H al unui graf orientat G este graful G însuşi sau se obţine din G prin suprimarea anumitor vârfuri şi a tuturor arcelor incidente cu acestea . Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri Y.

Astfel,subgraful grafului G din figura ,indus de mulţimea de vârfuri Y1

={1,2,4,5} are ca mulţime de arce mulţimea V1 ={(1,2), (2,4), (4,5)},iar subgraful indus de mulţimea de vârfuri Y2 ={6,7,8} are mulţimea arcelor V2={(7,6),(6,8),(7,8),(8,7)}.

Un graf orientat este complet dacă oricare două vârfuri sunt adiacente.În timp ce în cazul neorientat un graf complet cu n vârfuri este unic

determinat, în cazul orientat exista mai multe grafuri complete cu un număr dat de vârfuri.Ele se deosebesc fie prin orientarea arcelor , fie prin faptul că între două vârfuri oarecare exista un arc sau două arce de sensuri contrare.

Un lanţ al unui graf orientat se defineşte ca un şir de arce:

5

L=[u1,u2,…..,up] Cu proprietatea că oricare arc uI din acest şir are comună o extremitate cu ui-1 , iar cealaltă extremitate este comună cu ui+1 pentru orice i=1,...,p-1.

Dacă toate arcele lanţului L au aceeaşi orientare ,care este dată de sensul deplasării de la x0 către xr lanţul se numeşte drum.

Deci un drum într-un graf orientat G=(X,U) este un şir de vârfuri notat :D=(x0,x1,...,xr)

cu proprietatea că (x0,x1), (x1,x2), .... , (xr-1,xr)U, deci sunt arce ale grafului.

Vârfurile x0 şi xr se numesc extremităţile drumului D. Dacă vârfurile x0 ,x1 , ... , xr sunt distincte două câte două, drumul D se numeşte elementar. Din aceste definiţii rezultă că orice drum este şi lanţ , dacă îl privim ca un şir de arce.

Un drum D=(x0, ... ,xr) poate fi interpretat ca fiind traseul unei daplasari pe arcele grafului în ordinea (x0,x1), (x1,x2), ... , (xr-1,xr).

De aceea drumul D de extremităţi x0 şi xr , se mai spune că este un drum de la x0 la xr .Dacă x0=xr şi toate arcele (x0,x1), (x1,x2), ... ,(xr-1,xr) sunt distincte două câte două, drumul D se numeşte circuit.

Dacă toate vârfurile circuitului, cu excepţia primului şi a ultimului vârf, sunt distincte două câte două, circuitul se numeşte elementar.

Noţiunile de conexitate şi de componenta conexa a unui graf orientat sunt similare cu cele de la grafurile neorientate , utilizând noţiunea de lanţ din cazul grafurilor orientate.

Astfel, un graf orientat G se numeşte conex dacă pentru oricare două vârfuri distincte x şi y există un lanţ de extremităţi x şi y în G. O componentă conexa C a unui graf orientat G se defineşte ca fiind un subgraf conex maximal al lui G , deci nu există nici un lanţ care să unească un vârf din C cu un vârf care nu aparţine lui C.

DRUMURI MINIME ȘI MAXIME ÎN GRAFURI ORIENTATE

O altă noţiune de conexitate care apare numai în cazul grafurilor orientate este aceea de conexitate tare: Un graf orientat G se numeşte tare conex

6

dacă pentru oricare două vârfuri distincte x şi y ale lui G există un drum (x, ... ,y) de la x la y .Deoarece putem schimba rolul lui x şi y uneori definiţia unui graf tare conex se bazează pe existenţa unui drum de la x la y şi a unui drum de la y la x pentru oricare două vârfuri distincte x şi y ale grafului.

Pentru grafurile orientate conexitatea tare implica conexitatea simplă , adică orice graf tare conex este şi conex.

O componentă tare conexa a unui graf orientat G se defineşte ca fiind un subgraf tare conex maximal C al lui G , deci nu există drumuri care să unească în ambele sensuri un vârf x din C cu un vârf y al lui G care nu aparţine lui C, pentru orice x şi y cu proprietăţile menţionate. Rezultă că orice graf tare conex are o singură componenta tare conexa care conţine toate vârfurile grafului.

Să considerăm o funcţie l definită pe mulţimea U a arcelor unui graf orientat G=(X,U) cu valori numere reale pozitive:

l :Ux xR, x 0}.

Această funcţie asociază oricărui arc u al grafului lungimea sa notata l(u). Dacă =(x, ... ,y) este un drum de la x la y în graful G, vom defini lungimea drumului în mod aditiv, prin egalitatea:

l()=u l(u),

adică lungimea unui drum este egală cu suma lungimilor arcelor sale.

Un drum de la x la y se va numi drum minim ( respectiv

maxim)lungimea drumului este minimul ( respectiv maximul) lungimilor drumurilor de la x la y , presupunând că mulţimea acestor drumuri este nevida. Totuşi între aceste două noţiuni de drum minim şi de drum maxim există o deosebire importanta .

Orice drum minim este elementar , deoarece în caz contrar dacă un vârf se repetă în şirul care defineşte drumul , subdrumul cuprins între două apariţii consecutive ale unui vârf poate fi eliminat şi obţinem un drum de lungime strict mai mică decât drumul presupus minim , ceea ce este absurd.

Deoarece mulţimea drumurilor elementare de la x la y este finită pentru oricare două vârfuri distincte x şi y , rezultă că un drum minim de la x la y va exista întotdeauna pentru oricare două vârfuri distincte x şi y ale unui graf tare conex .

7

Pentru tratarea problemelor de minim vom asocia graful G o matrice a costurilor C=(cij)nn definită astfel :

l(xi ,xj) daca (xi , xj)U

Cij= 0 daca i=j

+ daca (xi ,xj)UIntuitiv,această alegere ar însemna că drumul cel mai scurt de la xi la el

însuşi este de lungime 0 iar inexistenta arcului ( xi, xj )este totuna cu existenţa unui arc de lungime infinită ( care evident nu va interveni niciodată într-un eventual drum minim de la xi la xj ) .

Algoritmul lui Dijkstra

Problemă: Fiind dat un graf orientat G=(X,U) , o funcţie l:UR+ şi un nod xi0 , să se determine pentru toate vârfurile x i pentru care există drum de la xi0 la xi , lungimea celui mai scurt drum precum şi unul dintre drumurile minime de la xi0 la xi.

Algoritmul utilizează metoda Greedy generând drumurile minime în ordinea crescătoare a lungimilor.

Exemplu:Pentru graful următor , considerând nodul de plecare 1 se vor obţine în

ordine:D1=(1,2) de lungime 1;D2=(1,2,5) de lungime 2;D3=(1,2,5,3) de lungime 4;D4=(1,2,5,3,4) de lungime 5;Deci pornind din nodul 1 avem în final :de la 1 la 2 D1 de lungime 1;de la 1 la 3 D3 de lungime 4;de la 1 la 4 D4 de lungime 5;de la 1 la 5 D2 de lungime 2;de la 1 la 6 nu există drum.

2 7

8

1 3 1 2

1 5 43

1 3 6

Se porneşte de la vârful xi0 . Evident cel mai scurt drum de la xi0 la unul dintre celelalte vârfuri ale grafului este dat de arcul (xi0 , xj) de lungime minimă . Următorul drum în ordinea lungimilor va fi dat fie de un alt arc cu extremitatea iniţială xi0 fie de un drum (xi0 ,xj ,xp). Alegem în continuare drumuri în ordinea crescătoare a lungimilor , până când am determinat drumuri minime de la xi0 către toate vârfurile pentru care există drum pornind din xi0.Pentru aceasta se considera S mulţimea vârfurilor xjX pentru care am găsit drum minim de la xi0 la xj. Iniţial S={ xi0 }. La fiecare pas , adăugăm în S acel nod xkX \S cu proprietatea că drumul minim de la xi0 la xk are cel mai mic cost dintre toate drumurile de la xi0 la xp , cu xpX\S.

Pentru exemplul considerat S va avea pe rând următorul conţinut:S={1}S={1,2}S={1,2,5}S={1,2,5,3}S={1,2,5,3,4}Să observăm că drumul minim de la xi0 la xk (xk nodul ce urmează să-l

adăugăm în S la un moment dat) trece numai prin vârfuri din S ( cu excepţia lui xk); într-adevăr notând xi primul vârf de pe acest drum ce nu aparţine lui S şi presupunând că xi xk ar rezulta că drumul de la xi0 la xi este mai scurt decât cel de la xi0 la xk ceea ce ar contrazice alegerea lui xk.

Pentru a alege nodul xk X\S ce urmează a fi adăugat în S vom folosi un vector d=( d1 , d2 , ... , dn ) astfel încât

lungimea drumului minim de la xi0 la xi , dacă xi Sdi= lungimea drumului minim de la xi0 la xi ce folosește numai

vârfuri din S dacă xi SInițial di=C(i0 ,i) i=1,n unde C este matricea costurilor .La un moment dat , adăugam în S nodul xk cu proprietatea că

dk=min{dj xjX S }.

După adăugarea lui xk în S trebuie actualizate valorile lui d pentru elementele care nu sunt în S , deoarece este posibil ca drumul minim de la xi0 la unul din aceste noduri ( folosind noduri din S ) să folosească nodul xk pe care tocmai l-am adăugat . Fie xj X|S un astfel de nod . Drumul minim de la xi0 la

9

xj ce foloseşte noduri din S ( inclusiv xk ) va fi de forma D=(xi0 , ... .... , xk , xj ). Într-adevăr, presupunând că există noduri intermediare xp pe drumul de la xk la xi

adică D=( xi0 , ... ,xk , ... ,xp , ... ,xj ) ar exista drumul mai scurt format din drumul minim de la xi0 la xp ( care evident nu conţine xk deoarece xp a fost adăugat mai înainte la mulţimea S ) şi secvenţă din D de la xp la xj. Deci pentru xjXS , dj se modifica după adăugarea lui xk la S numai dacă

dk+C(k,j)< , caz în care dj: +C(k,j). În final , vectorul va conţine costurile ( lungimile ) drumurilor minime de

la xi0 la celelalte noduri ; dacă pentru un nod xj nu există drum de la xi0 la xj, dj= .

Mai jos este prezentat algoritmul în limbaj Pascal. Pentru reprezentarea mulţimii S s-a folosit vectorul caracteristic S cu n componente

S[i]= 0 daca xiS 1 daca xiS

Ca mulţime de noduri se consideră X={1,2, ... ,n} iar lungimile arcelor se consideră numere întregi

program Dijkstra;const nmax=15;

inf=maxint div 2;var c:array[1..nmax , 1..nmax] of integer;

k,i,j,arc,m,n,x,y,z,xp: intrger; s,d,prec:array[1..nmax] of integer g: boolean;procedure min(var k: integer);var m,i: integer;beginm:=inf*2;for i:=1 to n do if (s[i]=0) and (d[i]<m) then

begin m:=d[i]; k:=i;

endend;

procedure drum(i:integer);begin

if i<>0 then begin

10

drum(prec[i]); write(i);

endelse writeln

end;begin writeln( dati nr de noduri ); readln (n); for i:=1 to n do

forj:=1 to n do c[i,j]:=inf;

for i:=1 to n do c[i,j]:=0;writeln ( dati nr de arce ); read (arc);for i:=1 to arc do begin write ( dati arcul ,i, si lungimea ); readln (x,y,z); c[x,y]:=z; end;read(xp);

for i:=1 to n do begin d[i]:=c[xp,i]; s[i]:=0; if c[xp,i]< inf then prec[i]:=xp else prec[i]:=0;

end;s[xp]:=1;prec[xp]:=0;g:=true;x:=0;repeat

min(k);x:=x+1;if (d[k]=inf) or (x=n) then g:=false

else begin s[k]:=1; for j:=1 to n do

if (s[j]=0)and (d[j]>d[k]+c[k,j]) then begind[j]:=d[k]+c[k,j];prec[j]:=k;end;

end;

11

until (not g);for i:= 1 to n do

if i<>xp then if d[i]=inf then

begin write(‘Nu exista drum de la ’,xp, ‘la’,i);writeln;endelse begin writeln(‘Drum minim de la ’,xp,’la’,i); drum(i); writeln end

end.

Algoritmul lui Roy- Floyd

Problemă: Fiind dat un graf G=(X,U) cu X={x1 , ... , xn} şi o funcţie l:UR+ să se determine pentru fiecare pereche de noduri xi , xj (ij) lungimea minimă a drumurilor de la xi la xj precum şi aceste drumuri (în caz că există drum de la xi la xj)

Algoritmul Roy –Floyd determina lungimile minime ale drumurilor între oricare două noduri ale grafului într-o matrice C=(cij)nn unde

CIJ = dacă i=jlungimea drumului minim de la xi la xj dacă există drum de la xi la xj

dacă nu există drum de la xi la xj

Determinarea mătricii C este asemănătoare algoritmului Roy-Warshallpentru obţinerea mătricii drumurilor

Se porneşte de la matricea costurilor Cfor k=1 to n for i=1 to n (ik) for j=1 to n (jk) cij : = min (cij , cik + ckj) endfor

12

endforendforObservaţie : Acest algoritm poate fi privit ca o succesiune de n

transformări aplicate mătricii C , o transformare k fiind astfel :Tk(A) = B, B =(bij)nn , bij= min(aij ,aik+a) i,j { 1 , ... , n}.

Simultan cu determinarea lungimilor minime ale drumurilor , pot fi reţinute şi acestea . Vom folosi o matrice D=(dij)nn ale cărei elemente dij sunt mulţimi de noduri (dij va reprezenta în final mulţimea nodurilor ce pot precede pe xj în drumul minim de la xi la xj).

Odată cu iniţializarea mătricii C cu matricea costurilor vom iniţializa şi matricea D astfel :

{xi} daca cij si i jdij=

daca cij= sau i=j Pe măsură ce se actualizează matricea C vom actualiza şi matricea D

după cum urmează :- dacă cij<cik+ckj , atunci dij rămâne neschimbat ;- dacă cij=cik+ckj (înseamnă că am găsit noi posibilităţi de

construire a drumului minim de la xi la xj folosind nodul k ) se adăugă la dij vârfurile din dkj ;

- dacă cij>cik+ckj se iniţializează dij cu dkj .În final reconstituirea drumurilor minime între oricare două vârfuri xi,xj se

face pornind din xj astfel : precedentul lui xj îl alegem din mulţimea dij având unul din aceste noduri fixat (să-l numim xg) precedentul acestuia va fi orice nod din mulţimea dig . Procedeul continua până ajungem la nodul xi .

Observaţie : Dacă ne interesează doar câte un drum pentru fiecare pereche de noduri xi , xj vom considera în locul mătricii D o matrice D tot nn astfel încât dij să reţină un nod ce-l poate precede pe xj în drumul minim de la xi

la xj . Mai jos este scris programul Pascal de determinare a tuturor drumuri-

lor minime între oricare două vârfuri ale unui graf G=(X,U) cu X={1 , ... , n}

program roymin;const nmax=20;

inf=maxint div 2;{inf poate fi initializat cu o valoare ce depaseste suma tuturor

costurilor}type multime = set of 1.. nmax;var c= array[1..nmax , 1..nmax] of word; {c initial matricea drumurilor} d: array [1..nmax , 1..nmax] of multime;

13

dr: array [1..nmax] of 1..nmax; n,m,i,j.k.lg:word;procedure initc; {initializeaza matricea costurilor C}var i,j,x,y,z: word;begin write(` Dati nr de noduri: `); readln(n); for i:=1 to n do begin

for j:=1 to n do c[i,j] := inf; c[i,i] :=0; end;write(`Dati nr de noduri : `);readln(m);for i:=1 to m do begin write(`Extremitatile si lungimea arcului `,i,`: `);

readln(x,y,z); c[x,y]:=z;

end; end; procedure initd; {iniţializeaza matricea D} var i,j:integer; begin for i:=1 to n do for j:=1 to n do if(c[i,j]<inf)and(i<>j) then d[i,j]=[i] else d[i,j]=[];

end;procedure drum(i,j:integer);

{genereaza in vectorul dr un drum minim de la i la j pornind din nodul j}var k: word ;begin if i<>j then begin

for k:=1 to n do if k in d[i,j] then

begin lg:=lg+1;dr[lg]:=k;drum(i,k);

14

lg:=lg – 1end;

endelse beginwriteln;for k:=lg downto 1 do

write(dr[k]:4)end;

end;

procedure afişare;var i,j:word;{afişarea rezultatelor}Begin

for i:= 1 to n dofor j:=1 to n dobeginwriteln:if c[i,j]=inf then

writeln(‘ nu exista drumuri minime de la ‘,i,’ la ‘,j,’)else

beginwriteln(‘ lungimea drumurilor minime de la ‘,i,’ la’,j,’ este

‘,c[i,j]);if i<> i then beginlg:=1;dr[1]:=jdrum(i,j)

endend

endend;begin

initc;initd;for k:=1 to n dofor i:=1 to n dofor j:=1 to n do

if c[i,j]>c[i,k]+c[k,j] thenbegin

15

c[i,j]:=c[i,k]+c[k,j]: d[i,j]:=d[k,j]end

else if c[i,j]=c[i,k]+c[k,j] then d[i,j]:=d[i,j]+d[k,j];

afişare;end.

DRUMURI MAXIME IN GRAFURI ORIENTATE

Fie G=(X,U) un graf fără circuite cu X={x1 , x2 ,... , xn} şi l:UR+ .Ne punem problema determinării drumurilor de lungime maximă în acest graf. Vom ataşa grafului G o matrice M=(mij)nn definită astfel :

l(xi , xj) daca (xi , xj)U

mij= - daca (xi , xj)U si (ij)

0 daca i=j

Observăm că aceasta matrice este asemănătoare mătricii costurilor ataşată grafului pentru determinarea drumurilor minime , cu diferenţa că pentru perechi de noduri xi , xj (ij) pentru care nu există arcul (xi,xj) marcăm în matrice - . Intuitiv , aceasta ar însemna că inexistenţa arcului (xi , xj) este totuna pentru studiul drumurilor maxime, cu existenţa unui arc de lungime - (care evident nu va interveni niciodată într-un eventual drum maxim de la xi la xj) .

Algoritmii de determinare a drumurilor minime pot fi adaptaţi cu mici modificări pentru determinarea drumurilor maxime. Considerând problema determinării drumurilor maxime între oricare două vârfuri xi , xj(ij) pentru care există drum de la xila xj , putem utiliza următorul algoritm:

Fie M matricea asociată grafului că mai sus , iar D=(dij)nn cu

{xi} daca mij>- si (ij)

16

dij= daca mij= - sau i=j

for k=1 to n for i=1 to n (ki) for j=1 to n (kj)

if mij<mik+mkj

then mij := mik+mkj dij := dkj

else if mij := mik+ mkj

then dij:= dij dkj

endifendif

endforendforendfor.

În matricea M vom avea în final lungimile drumurilor maxime între oricare 2 noduri iar în dij i ,j{1 , ... , n} vom avea mulţimea nodurilor ce pot precede pe xj într-un drum maxim de la xi la xj.

Mai jos este dat programul Pascal de determinare a tuturor drumurilor maxime între oricare două noduri folosind algoritmul prezentat anterior , pentru un graf G=(X, U) , X={1 , ... , n} .

program roymax;const nmax=20; inf=-(maxint div 2);type multime = set of 1 .. nmax;var c: array [1 .. nmax , 1 .. nmax] of integer;

{c initial matricea costurilor} d: array [1 .. nmax , 1 .. nmax] of multime; dr: array[1 .. nmax] of 1 .. nmax; n,m,i,j,k,lg:word;procedure initc;

{initializeaza matricea costurilor C} var i,j,x,y,z:word; begin write(Dati nr de noduri:);

readln(n); for i:=1 to n do begin for j:=1 to n do

17

c[i,j]:= inf; c[i,j]:=0 end;

write(Dati nr de ace :);readln(m);for i:=1 to m do begin

write(Extremitatile si lungimea arcului,i, :); readln(x,y,z); c[x,y] :=z;

endend;procedure initd ; {initializeaza matricea D}var i,j : integer ;begin for i:=1 to n do for j:=1 to n do

if (c[i,j]> inf) and (i<>j) then d[i,j]:=[i]else d[i,j]:=[];

end;prodcedure drum(i,j:integer);var k:word;begin if i<>j then

beginfor k:=1 to n do if k in d[i,j] then

begin lg:= lg+1;dr[lg]:=k;drum(i,k), lg:=lg-1end;

end else begin

writeln;for k:=lg downto 1 do

write(dr[k]:4)end;

end;procedure afisare;var i,j:word;begin

18

for i:=1 to n do for j:=1 to n do begin writeln;if c[i,j]=inf then

writeln( nu exista drum intre ,i, si ,j)else begin

writeln(Lungimea drumurilor maxime de la’,i,’la’,j,’ este ‘,c[i,j]);

if i<>j then begin lg:=1; dr[1]:=j; drum(i,j) endend

endend;begininitc;initd;for k:=1 to n do

for i:=1 to n do for j:=1 to n do if (c[i,k]<>inf) and (c[k,j]<>inf) then if (c[i,j]<c[i,k]+c[k,j] ) then

beginc[i,j]:=c[i,k]+c[k,j]; d[i,j]:=d[k,j];end

elseif c[i,j]=c[i,k]+c[k,j] then d[i,j]:=d[i,j]+d[k,j];

afisare;end.

Grafuri euleriene

19

Adeseori suntem tentaţi să credem simplul fapt de a traversa străzi sau poduri nu implică nici o idee deosebită. Iată însă că există o celebră problemă de traversare în care singura idee implicată este aceea de “traversare”, problema celor şapte poduri din Königsberg. Această banală şi totuşi foarte controversată problemă a dus la apariţia şi dezvoltarea teoriei grafurilor.

Problema se pune cam aşa:Oraşul Königsberg era aşezat pe coasta Mării Baltice, la gurile râului Pregel. Pe râu erau două insule legate de ţărmuri şi între ele de şapte poduri ca în figura 1.

Oamenii care cutreierau aceste insule au observat că dacă porneau de pe malul sudic al râului, nu puteau să-şi planifice plimbarea astfel încât să traverseze fiecare pod o singură dată. Se părea că ori trebuia să sară un pod ori să-l traverseze de două ori.În anul 1735 Euler a descoperit că nu mai are rost să se încerce, propunând următoarea analiză a problemei, din punct de vedere matematic:Să considerăm mai întâi insula estică (fig.2.):

sunt trei poduri care duc la ea. Deoarece se pleacă de pe malul sudic, înseamnă că se pleacă din afara insulei estice. Deoarece fiecare din cele trei traversări trebuie efectuate o singură dată,

20

Figura 1.

Fig.3

plimbarea trebuiesă se termine pe insula estică.

Să considerăm acum insula vestică: sunt cinci poduri care duc pe ea, iar cinci este din nou număr impar. Aşadar plimbarea începe în afara

insulei, şi deci trebuie să se termine pe insula vestică. Aceasta înseamnă că plimbarea se termină în două locuri diferite simultan ceea ce e imposibil. Soluţia dată de Euler

este tipică pentru personalitatea şi ingeniozitatea sa. Tot el a scris în anul 1736 prima lucrare de teorie a grafurilor despre problema acestor şapte poduri.

Un ciclu al unui graf G care conţine toate muchiile lui G se numeşte ciclu eulerian. Un graf G care are un ciclu eulerian se numeşte graf eulerian.Un graf G fără vârfuri izolate este eulerian dacă şi numai dacă este conex şi gradele tuturor vârfurilor sale sunt numere pare.Din punct de vedere al teoriei grafurilor, problema se pune cam aşa: cele patru regiuni (insule şi maluri) A,B,C,D şi cele şapte poduri le reprezentăm în graful următor (fig.3.):

Muchiile grafului reprezentând posibilităţile de trecere de pe un mal pe un pod şi reciproc.Problema are soluţie dacă acest graf conţine un ciclu eulerian. Un astfel de ciclu, utilizează la fiecare trecere printr-un vârf două muchii ce nu mai pot fi folosite pentru o nouă trecere. Cum fiecare dintre cele patru vârfuri (A,B,C,D) au grade impare, rezultă că ultima muchie va rămâne nefolosită sau va fi folosită pentru a face trecerea de final ( pentru a încheia plimbarea). Aceasta ar

21

însemna că ori va rămâne la unul din vârfuri, o muchie nefolosită (fapt ce demonstrează că nu avem un ciclu eulerian) ori plimbarea ar trebui să se termine în mai multe locuri simultan ceea ce e iarăşi imposibil.

Ciclu eulerian: Fiind dat un graf neorientat, să se verifice dacă este graf eulerian şi în caz afirmativ, să se determine un ciclu eulerian al său.

Explicaţia programului:Pornim dintr-un vârf neizolat reţinut cu ajutorul variabilei prim, în cadrul

procedurii de citire, apoi căutăm un ciclu eulerian al grafului printr-un algoritm backtracking. Vom folosi pentru reţinerea ordinii vârfului în ciclul eulerian un şir s.

În cadrul procedurii de cititre a matricii de adiacenţă, numărăm şi muchiile grafului cu ajutorul variabilei m.

Funcţia valid verifică dacă vârful k aparţine ciclului eulerian (dacă este adiacent cu vârful anterior determinat, iar în cazul în care este ultimul vârf k=m dacă este adiacent cu primul vâfr al ciclului).

Procedura back caută succesiv, autoapelându-se, vârfuri adiacente cu vârful anterior determinat până când se ajunge la ultimul vârf al ciclului (k=m); în acest caz, variabila booleană găsit care a fost iniţializată pe false, ia valoarea true şi este tipărit şirul s încheindu-l cu primul vârf al său (pentru a arăta că este un ciclu).

Dacă nu a fost găsit nici un ciclu eulerian al grafului dat (găsit=false), atunci graful nu este eulerian şi se tipăreşte mesaj.

Acelaşi lucru se întâmplă şi dacă graful nu are vârfuri 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]);

22

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;

23

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.

În viaţa de zi cu zi rezolvăm adesea, fără să ne dăm seama probleme de grafuri euleriene, de exemplu când vrem să mergem cu trenul în circuit şi vrem să plătim mai puţin, calculăm în aşa fel încât să trecem peste tot şi să plătim mai puţin. Dar aceasta nu o facem numai noi şi poştaşii, ci grafurile se utilizează la calcularea poziţilor optime de amplasare a sateliţilor de comunicaţie pentru ca informaţia transmisă să folosească mai puţin timp.

Grafuri hamiltoniene

Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar care contine toate varfurile grafului.Un graf care contine un ciclu hamiltonian se numeste graf hamiltonian.Un lant elementar care contine toate varfurile grafului se numeste lant hamiltonian.

24

* Un graf hamiltonian are cel putin trei varfuri. * Graful complet cu n varfuri este un graf hamiltonian.

Teoremă:

Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al grafului si d(x)>=n/2, atunci graful este hamiltonian.

drum hamiltonian: un drum elementar care trece prin toate nodurile grafului; circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

În timp, s-au evidenţiat o multitudine de probleme reductibile la găsirea unui drum (sau circuit) hamiltonian într-un graf, cum ar fi:

1. Problema poştaşului (găsirea traseului cel mai scurt care trece pe la toate locuinţele ce aparţin de oficiul poştal la care lucrează acesta); 2. Problema adunării deşeurilor (cel mai scurt drum care trece pe la toate

punctele de depozitate a deşeurilor);

3. Problema succesiunii operaţiilor (executarea mai multor operaţii pe o maşină în acea ordine în care suma timpilor consumaţi cu pregătirea maşinii pentru trecerea de la o operaţie la următoarea să fie minim) 4. Ordinea lipirii unor componente electronice pe o placă, etc;

Determinarea drumurilor hamiltoniene Problema determinării drumului (circuitului) hamiltonian de valoare optimă s-a dovedit deosebit de dificilă, neexistând nici acum un algoritm care să rezolve problema în timp polinomial şi nici măcar o metodă simplă prin care să se decidă dacă într-un graf dat există sau nu drumuri hamiltoniene. Există însă mai mulţi algoritmi, unii exacţi alţii heuristici, care reuşesc, într-un caz sau altul, să rezolve problema satisfăcător şi în timp util.

Teorema Dacă într-un graf orientat fără circuite există un drum hamiltonian atunci acesta este unic. Demonstraţie Deoarece un drum hamiltonian se identifică cu o permutare a nodurilor grafului, existenţa a două drumuri hamiltoniene implică existenţa a două permutări distincte a nodurilor grafului şi cum două permutări distincte

25

diferă prin cel puţin o inversiune vor exista două noduri xi şi xj în ordinea xi → xj

pe un drum şi invers pe celălalt, existând deci un drum atât de la xi la xj cât şi de la xj la xi, cele două formând împreună un circuit, în contradicţie cu ipoteza.

Graful din figura 1. Este hamiltonian, deoarece ciclul C=[1,2,3,5,4,1] este elementar (pleaca din varful 1 si se incheie tot in 1, iar muchiile [1,2], [2,3], [3,5], [5,4] si [4,1] sunt distincte doua cate doua) si in plus contine toate varfurile.

BIBLIOGRAFIE

1. Manual de informatica pentru clasa a XI-a , George Daniel Mateescu / Pavel Florin Moraru, Editura Niculescu , 2004

2. Metoda backtracking cu exemple in limbajul Pascal , Tiberiu Socaciu , Editura Edusoft , 2005

26

27

28

29