Grafuri Orientate

MINISTERUL EDUCAIEI,CERCETRII,TINERETULUI I SPORTULUI

COLEGIUL TEHNIC MTSARI

ATESTAT PROFESIONALProf.ndrumtor:

Sceanu IonElev:Vlsan Alina Corina

Profil:Matematica-Informatic

Colegiul Tehnic Mtsari

2015MINISTERUL EDUCAIEI,CERCETRII,TINERETULUI I SPORTULUI

COLEGIUL TEHNIC MTSARI

DRUMURI N GRAFURI ORIENTATE

Prof.ndrumtor:

Sceanu IonElev:Vlsan Alina Corina

Profil:Matematica-Informatic

Colegiul Tehnic Mtsari

2015CUPRINSArgument.4Grafuri orientate 5Drumuri minime i maxime n grafuri orientate7 Altgoritmul lui Dijkstra9Altgoritmul lui Roy-Floid13Drumuri maxime n grafuri orientate17Grafuri euleriene20 Grafuri hamiltoniene25Bibliografie27Argument

Informatica este tiina procesrii sistematice a informaiei. n special a procesrii cu ajutorul calculatoarelor. Istoric, informatica s-a dezvoltat ca tiin din matematic, n timp ce dezvoltarea primelor calulatoare i are originea n electrotehnic i telecomunicaii. De aceea, calculatorul reprezint doar dispozitivul pe care sunt implementate conceptele teoretice. Informaticianul olandez Edsger Dijkstra afirm: 'n Informatic ai de-a face cu calculatorul, cum ai n astronomie cu telescopul'.

Informatica teoretic se ocup cu studiul 'teoriei limbajelor formale', respectiv automatic, 'teoria computaional i complexitii','criptologie', 'logic','teoria grafurilor' punnd bazele pentru construirea compilatoarelor pentru limbajele de programare i pentru formalizarea problemelor din matematic. Ea este, prin urmare, coloana vertebral a informaticii.

Am ales aceast tem deoarece sunt pasionat de informatic i am studiat la orele de informatic grafurile.Grafuri orientate

Noiuni de bazUn graf orientat G este format dintr-o pereche ordonat de mulimi G= (X, U). ca i n cazul grafurilor neorientate, X este mulimea vrfurilor sau nodurilor grafului. Mulimea 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 vrful x este extremitatea iniial a arcului u, iar vrful y este extremitatea final a arcului u. Spre deosebire de cazul grafurilor neorientate, notaiile (x, y) i (y, x) vor desemna doua arce diferite.

Dac graful G conine arcul (x, y) vom spune c vrfurile x i y sunt adiacente n G i amndou sunt incidente cu arcul (x, y). Deci, un graf orientat G poate fi imaginat c o mulime de vrfuri, dintre care unele sunt unite dou cte dou prin arce. Un graf orientat poate fi desenat n plan reprezentnd vrfurile sale prin puncte i arcele prin sgei care sunt orientate de la extremitatea iniial ctre extremitatea final a fiecrui 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:

2 u5 4

u1

1

u3 u4

u7

u2

3

u6

5

Vom nota arcele aa cum se indic n figur , adic u1=(1,2), u2=(3,1),., u11=(6,8).

Gradul exterior al unui vrf x, notat prin d+(x), este numrul arcelor de form (x,y) cu yX. Gradul exterior al unui vrf x, notat prin d-(x),este numrul arcelor de form (y,x) cu yX.

Un graf parial al unui graf orientat G=(X,U) se definete n acelai mod ca i n cazul neorientat. El este un graf G1=(X,V) unde VU, deci este graful G nsui sau se obine din G prin suprimarea anumitor arce.

i definiia unui subgraf al unui graf orientat G=(X,U) este asemntoare cu cazul neorientat.Prin definiie , 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 extremiti n mulimea de vrfuri Y.

Deci un subgraf H al unui graf orientat G este graful G nsui sau se obine din G prin suprimarea anumitor vrfuri i a tuturor arcelor incidente cu acestea .

Vom spune c subgraful H este indus sau generat de mulimea de vrfuri Y.

Astfel,subgraful grafului G din figura ,indus de mulimea de vrfuri Y1 ={1,2,4,5} are ca mulime de arce mulimea V1 ={(1,2), (2,4), (4,5)},iar subgraful indus de mulimea de vrfuri Y2 ={6,7,8} are mulimea arcelor V2={(7,6),(6,8),(7,8),(8,7)}.

Un graf orientat este complet dac oricare dou vrfuri sunt adiacente.

n timp ce n cazul neorientat un graf complet cu n vrfuri este unic determinat, n cazul orientat exista mai multe grafuri complete cu un numr dat de vrfuri.Ele se deosebesc fie prin orientarea arcelor , fie prin faptul c ntre dou vrfuri oarecare exista un arc sau dou arce de sensuri contrare.

Un lan al unui graf orientat se definete ca un ir de arce:

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 lanului L au aceeai orientare ,care este dat de sensul deplasrii de la x0 ctre xr lanul se numete drum.

Deci un drum ntr-un graf orientat G=(X,U) este un ir de vrfuri notat :

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

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

Vrfurile x0 i xr se numesc extremitile drumului D. Dac vrfurile x0 ,x1 , ... , xr sunt distincte dou cte dou, drumul D se numete elementar. Din aceste definiii 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 extremiti 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 cte dou, drumul D se numete circuit.

Dac toate vrfurile circuitului, cu excepia primului i a ultimului vrf, sunt distincte dou cte dou, circuitul se numete elementar.

Noiunile de conexitate i de componenta conexa a unui graf orientat sunt similare cu cele de la grafurile neorientate , utiliznd noiunea de lan din cazul grafurilor orientate.

Astfel, un graf orientat G se numete conex dac pentru oricare dou vrfuri distincte x i y exist un lan de extremiti x i y n G. O component conexa C a unui graf orientat G se definete ca fiind un subgraf conex maximal al lui G , deci nu exist nici un lan care s uneasc un vrf din C cu un vrf care nu aparine lui C.

DRUMURI MINIME I MAXIME N GRAFURI ORIENTATE

O alt noiune de conexitate care apare numai n cazul grafurilor orientate este aceea de conexitate tare: Un graf orientat G se numete tare conex dac pentru oricare dou vrfuri 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 definiia unui graf tare conex se bazeaz pe existena unui drum de la x la y i a unui drum de la y la x pentru oricare dou vrfuri 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 definete ca fiind un subgraf tare conex maximal C al lui G , deci nu exist drumuri care s uneasc n ambele sensuri un vrf x din C cu un vrf y al lui G care nu aparine lui C, pentru orice x i y cu proprietile menionate. Rezult c orice graf tare conex are o singur componenta tare conexa care conine toate vrfurile grafului.

S considerm o funcie l definit pe mulimea U a arcelor unui graf orientat G=(X,U) cu valori numere reale pozitive:

l :Ux xR, x 0}.

Aceast funcie asociaz oricrui 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 ( respectivmaxim)lungimea drumului este minimul ( respectiv maximul) lungimilor drumurilor de la x la y , presupunnd c mulimea acestor drumuri este nevida. Totui ntre aceste dou noiuni de drum minim i de drum maxim exist o deosebire importanta .

Orice drum minim este elementar , deoarece n caz contrar dac un vrf se repet n irul care definete drumul , subdrumul cuprins ntre dou apariii consecutive ale unui vrf poate fi eliminat i obinem un drum de lungime strict mai mic dect drumul presupus minim , ceea ce este absurd.

Deoarece mulimea drumurilor elementare de la x la y este finit pentru oricare dou vrfuri distincte x i y , rezult c un drum minim de la x la y va exista ntotdeauna pentru oricare dou vrfuri distincte x i y ale unui graf tare conex .

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 nsui este de lungime 0 iar inexistenta arcului ( xi, xj )este totuna cu existena 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 funcie l:UR+ i un nod xi0 , s se determine pentru toate vrfurile xi 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 genernd drumurile minime n ordinea cresctoare a lungimilor.

Exemplu:

Pentru graful urmtor , considernd nodul de plecare 1 se vor obine 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

1 3

1 2

1 5 4

3

1 3

6

Se pornete de la vrful xi0 . Evident cel mai scurt drum de la xi0 la unul dintre celelalte vrfuri ale grafului este dat de arcul (xi0 , xj) de lungime minim . Urmtorul drum n ordinea lungimilor va fi dat fie de un alt arc cu extremitatea iniial xi0 fie de un drum (xi0 ,xj ,xp). Alegem n continuare drumuri n ordinea cresctoare a lungimilor , pn cnd am determinat drumuri minime de la xi0 ctre toate vrfurile pentru care exist drum pornind din xi0.Pentru aceasta se considera S mulimea vrfurilor xjX pentru care am gsit drum minim de la xi0 la xj. Iniial S={ xi0 }. La fiecare pas , adugm 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 rnd urmtorul coninut:

S={1}

S={1,2}

S={1,2,5}

S={1,2,5,3}

S={1,2,5,3,4}

S observm c drumul minim de la xi0 la xk (xk nodul ce urmeaz s-l adugm n S la un moment dat) trece numai prin vrfuri din S ( cu excepia lui xk); ntr-adevr notnd xi primul vrf de pe acest drum ce nu aparine lui S i presupunnd c xi xk ar rezulta c drumul de la xi0 la xi este mai scurt dect cel de la xi0 la xk ceea ce ar contrazice alegerea lui xk.

Pentru a alege nodul xk X\S ce urmeaz a fi adugat n S vom folosi un vector d=( d1 , d2 , ... , dn ) astfel nct

lungimea drumului minim de la xi0 la xi , dac xi( S

di= lungimea drumului minim de la xi0 la xi ce folosete numai

vrfuri din S dac xi( S

Iniial di=C(i0 ,i)( i=1,n unde C este matricea costurilor .

La un moment dat , adugam n S nodul xk cu proprietatea c

dk=min{dj ( xj(X( S }.

Dup adugarea 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 adugat . Fie xj X|S un astfel de nod . Drumul minim de la xi0 la xj ce folosete noduri din S ( inclusiv xk ) va fi de forma D=(xi0 , ... .... , xk , xj ). ntr-adevr, presupunnd 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 conine xk deoarece xp a fost adugat mai nainte la mulimea S ) i secven din D de la xp la xj. Deci pentru xjXS , dj se modifica dup adugarea lui xk la S numai dac

dk+C(k,j)< , caz n care dj: +C(k,j).

n final , vectorul va conine 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 mulimii S s-a folosit vectorul caracteristic S cu n componente

S[i]= 0 daca xi(S

1 daca xi(S

Ca mulime 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;

begin

m:=inf*2;

for i:=1 to n do

if (s[i]=0) and (d[i]d[k]+c[k,j]) then

begin

d[j]:=d[k]+c[k,j];

prec[j]:=k;

end;

end;

until (not g);

for i:= 1 to n do

if ixp then

if d[i]=inf then

begin

write(Nu exista drum de la ,xp, la,i);

writeln;

end

else 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 funcie 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=j

lungimea 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 mtricii C este asemntoare algoritmului Roy-Warshall

pentru obinerea mtricii drumurilor

Se pornete de la matricea costurilor C

for k=1 to n

for i=1 to n (ik)

for j=1 to n (jk)

cij : = min (cij , cik + ckj)

endfor

endfor

endfor

Observaie : Acest algoritm poate fi privit ca o succesiune de n transformri aplicate mtricii 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 reinute i acestea . Vom folosi o matrice D=(dij)nn ale crei elemente dij sunt mulimi de noduri (dij va reprezenta n final mulimea nodurilor ce pot precede pe xj n drumul minim de la xi la xj).

Odat cu iniializarea mtricii C cu matricea costurilor vom iniializa i matricea D astfel :

{xi} daca cij( ( si i( j

dij=

( daca cij=( sau i=j

Pe msur ce se actualizeaz matricea C vom actualiza i matricea D dup cum urmeaz :

dac cijcik+ckj se iniializeaz dij cu dkj .

n final reconstituirea drumurilor minime ntre oricare dou vrfuri xi,xj se face pornind din xj astfel : precedentul lui xj l alegem din mulimea dij avnd unul din aceste noduri fixat (s-l numim xg) precedentul acestuia va fi orice nod din mulimea dig . Procedeul continua pn ajungem la nodul xi .

Observaie : Dac ne intereseaz doar cte un drum pentru fiecare pereche de noduri xi , xj vom considera n locul mtricii D o matrice D tot nn astfel nct dij s rein 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 vrfuri 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;

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;

{iniializeaza matricea D}

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to n do

if(c[i,j]c[i,k]+c[k,j] then

begin

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];

afiare;

end.

DRUMURI MAXIME IN GRAFURI ORIENTATE

Fie G=(X,U) un graf fr circuite cu X={x1 , x2 ,... , xn} i l:UR+ .

Ne punem problema determinrii drumurilor de lungime maxim n acest graf. Vom ataa grafului G o matrice M=(mij)nn definit astfel :

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

mij= - ( daca (xi , xj)(U si (i(j)

0 daca i=j

Observm c aceasta matrice este asemntoare mtricii costurilor ataat grafului pentru determinarea drumurilor minime , cu diferena c pentru perechi de noduri xi , xj (ij) pentru care nu exist arcul (xi,xj) marcm n matrice - . Intuitiv , aceasta ar nsemna c inexistena arcului (xi , xj) este totuna pentru studiul drumurilor maxime, cu existena 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 adaptai cu mici modificri pentru determinarea drumurilor maxime. Considernd problema determinrii drumurilor maxime ntre oricare dou vrfuri xi , xj(ij) pentru care exist drum de la xila xj , putem utiliza urmtorul algoritm:

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

{xi} daca mij>-( si (i(j)

dij=

daca mij= -( sau i=jfor k=1 to n

for i=1 to n (k(i)

for j=1 to n (k(j)

if mij inf) and (ij) then d[i,j]:=[i]

else d[i,j]:=[];

end;

prodcedure drum(i,j:integer);

var k:word;

begin

if ij 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),

lg:=lg-1

end;

end

else begin

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 ij then begin

lg:=1;

dr[1]:=j;

drum(i,j)

end

end

end

end;

begin

initc;

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]=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 evideniat o multitudine de probleme reductibile la gsirea unui drum (sau circuit) hamiltonian ntr-un graf, cum ar fi:

1. Problema potaului (gsirea traseului cel mai scurt care trece pe la toate locuinele ce aparin de oficiul potal la care lucreaz acesta);

2. Problema adunrii deeurilor (cel mai scurt drum care trece pe la toate punctele de depozitate a deeurilor);

3. Problema succesiunii operaiilor (executarea mai multor operaii pe o main n acea ordine n care suma timpilor consumai cu pregtirea mainii pentru trecerea de la o operaie la urmtoarea s fie minim)

4. Ordinea lipirii unor componente electronice pe o plac, etc;

Determinarea drumurilor hamiltoniene Problema determinrii drumului (circuitului) hamiltonian de valoare optim s-a dovedit deosebit de dificil, neexistnd nici acum un algoritm care s rezolve problema n timp polinomial i nici mcar o metod simpl prin care s se decid dac ntr-un graf dat exist sau nu drumuri hamiltoniene.

Exist ns mai muli algoritmi, unii exaci alii heuristici, care reuesc, ntr-un caz sau altul, s rezolve problema satisfctor i n timp util.

Teorema Dac ntr-un graf orientat fr circuite exist un drum hamiltonian atunci acesta este unic.

Demonstraie Deoarece un drum hamiltonian se identific cu o permutare a nodurilor grafului, existena a dou drumuri hamiltoniene implic existena a dou permutri distincte a nodurilor grafului i cum dou permutri distincte difer prin cel puin o inversiune vor exista dou noduri xi i xj n ordinea xi xj pe un drum i invers pe cellalt, existnd deci un drum att de la xi la xj ct i de la xj la xi, cele dou formnd mpreun un circuit, n contradicie 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

Figura 1.

Fig.3

PAGE 4