GRAFURI ORIENTATENotiuni de baza

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau nodurilor grafului.Multimea U este formata din perechi ordonate de elemente distincte din X, numite arce.

Orice arc u U va fi notat prin u=(x,y) cu x,yX si xy.Spunem ca varful x este extremitatea initiala a arcului u, iar varful y

este extremitatea finala a arcului u. Spre deosebire de cazul grafurilor neorientate, notatiile(x,y) si (y,x) vor desemna doua arce diferite.

Daca graful G contine arcul (x,y) vom spune ca varfurile x si y sunt adiacente in G si amandoua sunt incidente cu arcul (x,y). Deci, un graf orientat G poate fi imaginat ca o multime de varfuri, dintre care unele sunt unite doua cate doua prin arce. Un graf orientat poate fi desenat in plan reprezentand varfurile sale prin puncte si arcele prin sageti care sunt orientate de la extremitatea initiala catre extremitatea finala a fiecarui arc.

Graful orientat G=(X,U) unde: X={ 1,2, …. ,8} si U={(1,2), (2,3), (3,1), (3,2), (2,4), (4,5), (3,5), (6,8), (8,7), (7,8),(7,6)} se reprezinta ca in figura:

2 u5 4

u1

1 u3 u4 u7

u2

3 u6 5

u1=(1,2), u2=(3,1),…., u11=(6,8).

1

Gradul exterior al unui varf x, notat prin d+(x), este numarul arcelor de forma (x,y) cu yX. Gradul interior al unui varf x, notat prin d-(x),este numarul arcelor de forma (y,x) cu yX.

Un graf partial al unui graf orientat G=(X,U) se defineste in acelasi mod ca si in cazul neorientat. El este un graf G1=(X,V) unde VU, deci este graful G insusi sau se obtine din G prin suprimarea anumitor arce.

Si definitia unui subgraf al unui graf orientat G=(X,U) este asemanatoare 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 extremiţaţi in mulţimea de varfuri Y. Deci un subgraf H al unui graf orientat G este graful G insuşi sau se obţine din G prin suprimarea anumitor varfuri si a tuturor arcelor incidente cu acestea . Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y.

Astfel,subgraful grafului G din figura ,indus de multimea de varfuri Y1

={1,2,4,5} are ca multime de arce multimea V1 ={(1,2), (2,4), (4,5)},iar subgraful indus de multimea de varfuri Y2 ={6,7,8} are multimea arcelor V2={(7,6),(6,8),(7,8),(8,7)}.

Un graf orientat este complet daca oricare doua varfuri sunt adiacente.In timp ce in cazul neorientat un graf complet cu n varfuri este unic

determinat, in cazul orientat exista mai multe grafuri complete cu un numar dat de varfuri.Ele se deosebesc fie prin orientarea arcelor , fie prin faptul ca intre doua varfuri oarecare exista un arc sau doua arce de sensuri contrare.

Un lant al unui graf orientat se defineste ca un sir de arce:L=[u1,u2,…..,up]

Cu proprietatea ca oricare arc uI din acest sir are comuna o extremitate cu ui-1 , iar cealalta extremitate este comuna cu ui+1 pentru orice i=1,...,p-1.

Daca toate arcele lantului L au aceeasi orientare ,care este data de sensul deplasarii de la x0 catre xr lantul se numeste drum.

Deci un drum intr-un graf orientat G=(X,U) este un sir de varfuri notat :

D=(x0,x1,...,xr)

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

2

Varfurile x0 si xr se numesc extremitatile drumului D. Daca varfurile x0 ,x1 , ... , xr sunt distincte doua cate doua, drumul D se numeste elementar. Din aceste definitii rezulta ca orice drum este si lant , daca il privim ca un sir de arce.

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

De aceea drumul D de extremitati x0 si xr , se mai spune ca este un drum de la x0 la xr .Daca x0=xr si toate arcele (x0,x1), (x1,x2), ... ,(xr-1,xr) sunt distincte doua cate doua, drumul D se numeste circuit.

Daca toate varfurile circuitului, cu exceptia primului si a ultimului varf, sunt distincte doua cate doua, circuitul se numeste elementar.

Notiunile de conexitate si de componenta conexa a unui graf orientat sunt similare cu cele de la grafurile neorientate , utilizand notiunea de lant din cazul grafurilor orientate.

Astfel, un graf orientat G se numeste conex daca pentru oricare doua varfuri distincte x si y exista un lant de extremitati x si y in G. O componenta conexa C a unui graf orientat G se defineste ca fiind un subgraf conex maximal al lui G , deci nu exista nici un lant care sa uneasca un varf din C cu un varf care nu apartine lui C.

Un graf orientat G se numeste tare conex daca pentru oricare doua varfuri distincte x si y ale lui G exista un drum (x, ... ,y) de la x la y .

Deoarece putem schimba rolul lui x si y uneori definitia unui graf tare conex se bazeaza pe existenta unui drum de la x la y si a unui drum de la y la x pentru oricare doua varfuri distincte x si y ale grafului.Pentru grafurile orientate conexitatea tare implica conexitatea simpla , adica orice graf tare conex este si conex.

O componenta tare conexa a unui graf orientat G se defineste ca fiind un subgraf tare conex maximal C al lui G , deci nu exista drumuri care sa uneasca in ambele sensuri un varf x din C cu un varf y al lui G care nu apartine lui C, pentru orice x si y cu proprietatile mentionate. Rezulta ca orice graf tare conex are o singura componenta tare conexa care contine toate varfurile grafului.

3

DRUMURI MINIME SI MAXIME IN GRAFURI ORIENTATE

O alta notiune de conexitate care apare numai in cazul grafurilor orientate este aceea de conexitate tare: Un graf orientat G se numeste tare conex daca pentru oricare doua varfuri distincte x si y ale lui G exista un drum (x, ... ,y) de la x la y .Deoarece putem schimba rolul lui x si y uneori definitia unui graf tare conex se bazeaza pe existenta unui drum de la x la y si a unui drum de la y la x pentru oricare doua varfuri distincte x si y ale grafului.

Pentru grafurile orientate conexitatea tare implica conexitatea simpla , adica orice graf tare conex este si conex.

O componenta tare conexa a unui graf orientat G se defineste ca fiind un subgraf tare conex maximal C al lui G , deci nu exista drumuri care sa uneasca in ambele sensuri un varf x din C cu un varf y al lui G care nu apartine lui C, pentru orice x si y cu proprietatile mentionate. Rezulta ca orice graf tare conex are o singura componenta tare conexa care contine toate varfurile grafului.

4

Sa consideram o functie l definita pe multimea U a arcelor unui graf orientat G=(X,U) cu valori numere reale pozitive:

l :Ux xR, x 0}.

Aceasta functie asociaza oricarui arc u al grafului lungimea sa notata l(u). Daca =(x, ... ,y) este un drum de la x la y in graful G, vom defini lungimea drumului in mod aditiv, prin egalitatea:

l()=u l(u),

adica lungimea unui drum este egala cu suma lungimilor arcelor sale.

Un drum de la x la y se va numi drum minim ( respectiv maxim)lungimeadrumului este minimul ( respectiv maximul)

lungimilor drumurilor de la x la y , presupunand ca multimea acestor drumuri este nevida. Totusi intre aceste doua notiuni de drum minim si de drum maxim exista o deosebire importanta .

Orice drum minim este elementar , deoarece in caz contrar daca un varf se repeta in sirul care defineste drumul , subdrumul cuprins intre doua aparitii consecutive ale unui varf poate fi eliminat si obtinem un drum de lungime strict mai mica decat drumul presupus minim , ceea ce este absurd.

Deoarece multimea drumurilor elementare de la x la y este finita pentru oricare doua varfuri distincte x si y , rezulta ca un drum minim de la x la y va exista intotdeauna pentru oricare doua varfuri distincte x si y ale unui graf tare conex .

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

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

Cij= 0 daca i=j

+ daca (xi ,xj)UIntuitiv,aceasta alegere ar insemna ca drumul cel mai scurt de la xi la

el insusi este de lungime 0 iar inexistenta arcului ( xi, xj )este totuna cu existenta unui arc de lungime infinita ( care evident nu va interveni niciodata intr-un eventual drum minim de la xi la xj ) .

5

Algoritmul lui Dijkstra

Problema: Fiind dat un graf orientat G=(X,U) , o functie l:UR+ si un nod xi0 , sa se determine pentru toate varfurile x i pentru care exista drum de la xi0 la xi , lungimea celui mai scurt drum precum si unul dintre drumurile minime de la xi0 la xi.

Algoritmul utilizeaza metoda Greedy generand drumurile minime in ordinea crescatoare a lungimilor.

Exemplu:Pentru graful urmator , considerand nodul de plecare 1 se vor obtine

in 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 in 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 exista drum.

2 7 1 3 1 2

1 5 43

1 3 6

Se porneste de la varful xi0 . Evident cel mai scurt drum de la xi0 la unul dintre celelalte varfuri ale grafului este dat de arcul (xi0 , xj) de lungime minima . Urmatorul drum in ordinea lungimilor va fi dat fie de un alt arc cu extremitatea initiala xi0 fie de un drum (xi0 ,xj ,xp). Alegem in continuare drumuri in ordinea crescatoare a lungimilor , pana cand am determinat drumuri minime de la xi0 catre toate varfurile pentru care exista drum pornind din xi0.Pentru aceasta se considera S multimea varfurilor xjX pentru care am gasit drum minim de la xi0 la xj. Initial S={ xi0 }. La fiecare

6

pas , adaugam in S acel nod xkX \S cu proprietatea ca 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 rand urmatorul continut:S={1}S={1,2}S={1,2,5}S={1,2,5,3}S={1,2,5,3,4}Sa observam ca drumul minim de la xi0 la xk (xk nodul ce urmeaza sa-l

adaugam in S la un moment dat) trece numai prin varfuri din S ( cu exceptia lui xk); intr-adevar notand xi primul varf de pe acest drum ce nu apartine lui S si presupunand ca xi xk ar rezulta ca drumul de la xi0 la xi este mai scurt decat cel de la xi0 la xk ceea ce ar contrazice alegerea lui xk.

Pentru a alege nodul xk X\S ce urmeaza a fi adaugat in S vom folosi un vector d=( d1 , d2 , ... , dn ) astfel incat

lungimea drumului minim de la xi0 la xi , daca xi Sdi= lungimea drumului minim de la xi0 la xi ce foloseste numai

varfuri din S daca xi SInitial di=C(i0 ,i) i=1,n unde C este matricea costurilor .La un moment dat , adaugam in S nodul xk cu proprietatea ca

dk=min{dj xjX S }.

Dupa adaugarea lui xk in S trebuie actualizate valorile lui d pentru elementele care nu sunt in S , deoarece este posibil ca drumul minim de la xi0

la unul din aceste noduri ( folosind noduri din S ) sa foloseasca nodul xk pe care tocmai l-am adaugat . Fie xj X|S un astfel de nod . Drumul minim de la xi0 la xj ce foloseste noduri din S ( inclusiv xk ) va fi de forma D=(xi0 , ... .... , xk , xj ). Intr-adevar, presupunind ca exista noduri intermediare xp pe drumul de la xk la xi adica D=( xi0 , ... ,xk , ... ,xp , ... ,xj ) ar exista drumul mai scurt format din drumul minim de la xi0 la xp ( care evident nu contine xk

deoarece xp a fost adaugat mai inainte la multimea S ) si secventa din D de la xp la xj. Deci pentru xjXS , dj se modifica dupa adaugarea lui xk la S numai daca

dk+C(k,j)< , caz in care dj: +C(k,j). In final , vectorul va contine costurile ( lungimile ) drumurilor minime

de la xi0 la celelalte noduri ; daca pentru un nod xj nu exista drum de la xi0 la xj, dj= .

7

Mai jos este prezentat algoritmul in limbaj Pascal. Pentru reprezentarea multimii S s-a folosit vectorul caracteristic S cu n componente

0 daca xiS

S[i]=1 daca xiS

Ca multime de noduri se considera X={1,2, ... ,n} iar lungimile arcelor se considera numere intregi.

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 drum(prec[i]); write(i);

endelse writeln

end;begin

8

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;until (not g);for i:= 1 to n do

if i<>xp then

9

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

Problema: Fiind dat un graf G=(X,U) cu X={x1 , ... , xn} si o functie l:UR+ sa se determine pentru fiecare pereche de noduri xi , xj (ij) lungimea minima a drumurilor de la xi la xj precum si aceste drumuri (in caz ca exista drum de la xi la xj)

Algoritmul Roy –Floyd determina lungimile minime ale drumurilor intre oricare doua noduri ale grafului intr-o matrice C=(cij)nn unde

CIJ = daca i=jlungimea drumului minim de la xi la xj daca exista drum de la xi la xj

daca nu exista drum de la xi la xj

Determinarea matricii C este asemanatoare algoritmului Roy-Warshallpentru obtinerea matricii drumurilor

Se porneste 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 endforendforObservatie : Acest algoritm poate fi privit ca o succesiune de n

transformari aplicate matricii C , o transformare k fiind astfel :

10

Tk(A) = B, B =(bij)nn , bij= min(aij ,aik+a) i,j { 1 , ... , n}.Simultan cu determinarea lungimilor minime ale drumurilor , pot fi

retinute si acestea . Vom folosi o matrice D=(dij)nn ale carei elemente dij

sunt multimi de noduri (dij va reprezenta in final multimea nodurilor ce pot precede pe xj in drumul minim de la xi la xj).

Odata cu initializarea matricii C cu matricea costurilor vom initializa si matricea D astfel :

{xi} daca cij si i jdij=

daca cij= sau i=j Pe masura ce se actualizeaza matricea C vom actualiza si matricea D

dupa cum urmeaza :- daca cij<cik+ckj , atunci dij ramane neschimbat ;- daca cij=cik+ckj (inseamna ca am gasit noi posibilitati de

construire a drumului minim de la xi la xj folosind nodul k ) se adauga la dij varfurile din dkj ;

- daca cij>cik+ckj se initializeaza dij cu dkj .In final reconstituirea drumurilor minime intre oricare doua varfuri

xi,xj se face pornind din xj astfel : precedentul lui xj il alegem din multimea dij

avand unul din aceste noduri fixat (sa-l numim xg) precedentul acestuia va fi orice nod din multimea dig . Procedeul continua pana ajungem la nodul xi .

Observatie : Daca ne intereseaza doar cate un drum pentru fiecare pereche de noduri xi , xj vom considera in locul matricii D o matrice D tot nn astfel incat dij sa retina un nod ce-l poate precede pe xj in drumul minim de la xi la xj .

Mai jos este scris programul Pascal de determinare a tuturor drumuri-lor minime intre oricare doua varfuri 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; dr: array [1..nmax] of 1..nmax; n,m,i,j.k.lg:word;

11

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;

12

drum(i,k);lg:=lg – 1

end; end

else beginwriteln;for k:=lg downto 1 do

write(dr[k]:4)end;

end;

procedure afişare;var i,j:word;{afişarea rezultatelor}beginfor 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;begininitc;initd;for k:=1 to n dofor i:=1 to n dofor j:=1 to n doif c[i,j]>c[i,k]+c[k,j] then

13

beginc[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 fara circuite cu X={x1 , x2 ,... , xn} si l:UR+ .Ne punem problema determinarii drumurilor de lungime maxima in acest graf. Vom atasa grafului G o matrice M=(mij)nn definita astfel :

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

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

0 daca i=j

Observam ca aceasta matrice este asemanatoare matricii costurilor atasata grafului pentru determinarea drumurilor minime , cu diferenta ca pentru perechi de noduri xi , xj (ij) pentru care nu exista arcul (xi,xj) marcam in matrice - . Intuitiv , aceasta ar insemna ca inexistenta arcului (xi

, xj) este totuna pentru studiul drumurilor maxime, cu existenta unui arc de lungime - (care evident nu va interveni niciodata intr-un eventual drum maxim de la xi la xj) .

Algoritmii de determinare a drumurilor minime pot fi adaptati cu mici modificari pentru determinarea drumurilor maxime. Considerind problema determinarii drumurilor maxime intre oricare doua varfuri xi , xj(ij) pentru care exista drum de la xila xj , putem utiliza urmatorul algoritm:

Fie M matricea asociata grafului ca mai sus , iar D=(dij)nn cu

14

{xi} daca mij>- si (ij)

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.

In matricea M vom avea in final lungimile drumurilor maxime intre oricare 2 noduri iar in dij i ,j{1 , ... , n} vom avea multimea nodurilor ce pot precede pe xj intr-un drum maxim de la xi la xj.

Mai jos este dat programul Pascal de determinare a tuturor drumurilor maxime intre oricare doua 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

15

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,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

16

writeln;for k:=lg downto 1 do

write(dr[k]:4)end;

end;procedure afisare;var i,j:word;begin 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];

17

afisare;end.

18

19

20