Grafuri+Orientate

8/4/2019 Grafuri+Orientate

1/30

1

GRAFURI ORIENTATE

ASPECTE TEORETICE

1. Noiunea de graf orientat

Definiie. Se numetegraf orientat o pereche ordonatde mulimi notatG=(V, U), unde:V : este o mulime, finiti nevid, ale crei elemente se numesc noduri sau vrfuri;

U : este o mulime, de perechi ordonate de elemente distincte din V, ale crei elemente se numesc arce.Exemplu de graf orientat:G=(V, U) unde: V={ 1,2,3,4}

U={{1,2}, {2,3},{1,4}}Demonstraie:

Perechea G este graf orientat deoarece respect ntocmai definiia prezentat mai sus, adic:V : este finiti nevid:U : este o mulime de perechi ordonate de elemente din V.

n continuare, vom nota submulimea {x,y}, care reprezintun arc, cu ( x,y) (ntr-un graf orientat arcul (x,y)este diferit de arcul ( y,x)). n baza celor spuse anterior, graful prezentat n exemplul de mai sus se reprezinttextual astfel:

G=(V, U) unde: V={ 1,2,3,4}U={(1,2), (2,3), (1,4) }

n teoria grafurilor orientate se ntlnesc frecvent noiunile:- extremitile unui arc fiind dat arcul u=(x,y), se numesc extremiti ale sale nodurile x i y;

x se numete extremitate iniial;y se numete extremitate final.

- vrfuri adiacente dac ntr-un graf exist arcul u=(x,y) (sau u=(y,x), sau amndou), se spune despre nodurile x i y c suntadiacente;- inciden

dac ul i u2 sunt dou arce ale aceluiai graf, se numesc incidente dac au o extremitate comun.

Exemplu. u1=(x,y) i u2=(y,z) sunt incidente; dac u1=(x,y) este un arc ntr-un graf, se spune despre el i nodul x, sau nodul y, c sunt incidente.

Reprezentarea unui graf orientat admite dou forme, i anume:- reprezentare textual: aa cum s-a reprezentat graful din exemplul anterior;- reprezentare grafic : arcele sunt reprezentate prin sgei orientate, iar nodurile prin puncte.Exemplu de graf orientat reprezentat textual:G=(V, U) unde: V={ 1,2,3,4}

U={(1,2), (2,3), (1,4), (4,1)}Exemplu de graf orientat reprezentat grafic (este graful de la exemplul anterior):

1

Alte definiii

Definiie.Se numetegraf orientat o pereche ordonatde mulimi notatG=(V, U), unde:V : este o mulime, finiti nevid, ale crei elemente se numesc noduri sau vrfuri;

U : este o mulime, de perechi ordonate de elemente din V, ale crei elemente se numesc arce.


2/30

2

Aceast definiie difer de prima definiie prin faptul ca acum nu se mai spune despre extremitile unui arcca trebuie s fie distincte. n baza acestei definiii, sunt permise i arce de genul: u=(x,x) unde xV; acestearce se numesc bucle.Exemplu de graf orientat (reprezentat grafic):V={1,2,3,4} U={(1,2),(2,3),(1,4), (4,4)}

1

Definiie.Se numetegraf orientat o pereche ordonatde mulimi notatG=(V, U), unde:V : este o mulime, finiti nevid, ale crei elemente se numesc noduri sau vrfuri;

U : este o familie de perechi ordonate de elemente din V, numitfamilia de arce.

Aceast definiie difer de cea anterioar prin faptul ca acum nu numai c se admit bucle, dar se admit i maimulte arce identice. Exemplu de graf orientat (reprezentat grafic):V={1,2 3,4}U={(1,2), (1,2), (2,1), (1,4), (2,3), (4,4)}

1

Observaie. Dac ntr-un graf orientat numrul arcelor identice nu depete numrul p, atunci senumete p-graf.

2. Noiunea de graf parial

Definiie. Fie G=(V, U) un graf orientat. Se numete graf parial, al grafului G, graful orientat G1=(V, U1)unde U1U.Atenie! Citind cu atenie definiia, de mai sus, tragem concluzia:

Un graf parial, al unui graf orientat G=(V, U), are aceeai mulime de vrfuri ca i G, iar mulimea arceloreste o submulime a lui U sau chiar U.

Exemplu: Fie graful orientatG=(V, U) unde: V={ 1,2,3,4}

U={(1,2), (l,4), (2,3)}reprezentat grafic astfel:

1. Un exemplu de graf parial al grafului G este

graful orientat:G1=(V, U1) unde: V={ 1,2,3,4}

U1={(1,2),(1,4)}(s-a eliminat arcul (2,3))

reprezentat grafic astfel:1

3

2. Un exemplu de graf parial al grafului G estegraful orientat:reprezentat grafic astfel:G1=(V, U) unde: V={ 1,2,3,4}

U1=(s-au eliminat toate arcele)1

42

3


3/30

3

Observaie. Fie G=(V, U) un graf orientat. Un graf parial, al grafului G, se obine pstrnd vrfurile ieliminnd eventual nite arce (se pot elimina i toate arcele sau chiar nici unul).

3. Noiunea de subgraf

Definiie.Fie G=(V, U) un graf orientat. Se numetesubgraf, al grafului G,graful orientat G1=(V1,U1)unde V1V iar U1 conine toate arcele din U care au extremitile n V1.


U={(1,2), (2,3), (1,4)}reprezentat grafic astfel:

1. Un exemplu de subgraf al grafului G estegraful orientat:G1=(V1, U1) unde: V1={1,2,3}

(s-a ters nodul4)U1={(1,2),(2,3)}(s-a eliminat arcul (1,4))

reprezentat grafic astfel:

2. Un exemplu de subgraf al grafului G este grafulorientat:G1=(V1, U1) unde: V1={2,3,4}

(s-a eliminat nodul 1)U1={(2,3)}(s-au eliminat arcele (1,4) (1,2))

reprezentat grafic astfel:4

Observaie. Fie G=(V, U) un graf orientat. Un subgraf, al grafului G, se obine tergnd eventual anumitevrfuri i odat cu acestea i arcele care le admit ca extremitate (nu se pot terge toate vrfurile deoareces-ar obine un graf cu mulimea vrfurilor vid).

4. Gradul unui vrf

Avnd la baz ideea c "raportat la un vrf exist arce care ies din acel vrfi arce care intr n acel vrf, auluat natere urmtoarele noiuni:

- grad exterior- grad interior

care vor fi prezentate in continuare.

Grad exterior

Definiie. Fie G=(V, U) un graf orientat si x un nod al su. Se numetegrad exterioral nodului x, numrularcelor de forma (x,y) (adicnumrul arcelor care ies din x), notatd

+(x).

Exemplu: Fie graful orientat:

G=(V, U) unde: V={ 1,2,3,4}U={(1,2), (1,2), (2,1), (1,4), (2,3)> (4,4)}reprezentat grafic astfel:

1

Gradul exterior al nodului 1 este d+(1)=3 (n graf, sunt trei arce care ies din 1).Gradul exterior al nodului 2 este d+(2)=2 (n graf, sunt dou arce care ies din 2).


4/30

4

Gradul exterior al nodului 3 este d+(3)=0 (n graf, nu sunt arce care ies din 3).Gradul exterior al nodului 4 este d+(4)=1 (n graf, este un arc care iese din 4 (bucla)).Observaii.1. Mulimea succesorilor lui x se noteaz cu +(x) i se reprezint astfel:

( ) ( ){ }UyxVyx =+ , 2. Mulimea arcelor ce ies din x se noteaz cu +(x) i se reprezint astfel:

( ) ( ){ }VyUyxx =+ , 3. Legat de cardinalele mulimilor+(x) i +(x) putem scrie:

( ) ( ) ( )xdxx+++

== Raportat la graful prezentat n figura de mai jos,

1

putem scrie:

+ (1)={2, 4} + (1)={(1,2), (1,4)} ( ) ( ) ( ) 2111 === +++ d

+ (2)={1, 3} + (2)={(2,1), (2,3)} ( ) ( ) ( ) 2222 === +++ d

+ (3)= + (3)= ( ) ( ) ( ) 0333 === +++ d

+ (4)={4} + (4)=f (4,4)} ( ) ( ) ( ) 1444 === +++ d

Grad interior

Definiie. Fie G=(V, U) un graf orientati x un nod al su. Se numetegrad interioral nodului x, numrularcelor de forma (y,x) ( adicnumrul arcelor care intr in x), notatd

-(x).


U= {(1,2), (1,2), (2,1), (1,4), (2,3), (4,4)}

reprezentat grafic astfel:

Gradul interior al nodului 1 este d -(1)=1 (n graf, este un arc care intr n 1).Gradul interior al nodului 2 este d - (2)=2 (n graf, sunt dou arce care intr n 2).Gradul interior al nodului 3 este d -(3)=1 (n graf, este un arc care intr n 3).Gradul interior al nodului 4 este d -(4)=2 (n graf, sunt dou arce care intr n 4).

Observaii.1. Mulimea predecesorilorlui x se noteaz cu -(x) i se reprezint astfel:( ) ( ){ }UxyVyx = ,

2. Mulimea arcelor ce intr in x se noteaz cu -(x) i se reprezint astfel:( ) ( ){ }VxUxyx = ,

3. Legat de cardinalele mulimilor-(x) i -(x) putem scrie:

( ) ( ) ( )xdxx ==

Raportat la graful prezentat n figura de mai jos,1


5/30

5

putem scrie:

- (1)={2} - (1)={(2,1)} ( ) ( ) ( ) 1111 === d

- (2)={1} - (2)={(1,2)} ( ) ( ) ( ) 1222 === d

- (3)={2} -(3) = {(2,3)} ( ) ( ) ( ) 1333 === d

- (4)={1,4} - (4)={(1,4),(4,4)} ( ) ( ) ( ) 2444 === d

Observaie. Un nod se numete izolat dac:d+(x)=d-(x)=0

Propoziie. n graful orientat G=(V, U), n care V={x1, x2, ...,xn} i sunt m arce, se verific egalitatea :

( ) ( ) mxdxdn

i

i

n

i

i==

=

=

+

11

5. Graf complet. Graf turneu

Definiie.Fie G=(V, U) un graf orientat. Graful G se numetegraf complet dacoricare dou vrfuridistincte ale sale sunt adiacente.Douvrfuri x i y sunt adiacente dac:

- ntre ele existarcul (x,y), sau

- ntre ele existarcul (y,x), sau

- ntre ele existarcele (x,y) i (y,x).

Exemplu de graf orientat complet:G=(V, U) unde: V={1,2,3,4}

U={(1,2),,(1,3), (1,4), (2,3), (2,4), (3,4)}Reprezentarea sa grafic este:

1

Propoziie. ntr-un graf complet cu n vrfuri, exist ntre2

)1( nni n(n-1) arce. (U este privit ca o mulime

(prima definiie a grafului) nu ca o familie)

Demonstraie: Numrul cel mai mic de arce, cnd graful este complet, se obine atunci cnd nodurile suntunite doar printr-un singur arc i se determin astfel:Pentru fiecare vrf xi, numrul arcelor care intri ies este n-1, deci d

+(xi)+ d-(xi)=n-1, pentru orice i=1..n.

nsumnd toate aceste relaii, obinem:

( ) ( )( ) ( ) ( ) ( ) )1(11111

=+=+ =

=

+

==

+nnxdxdnxdxd

n

i

i

n

i

i

n

i

n

i

ii (1)

innd cont de faptul c:

( ) ( ) mxdxdn

i

i

n

i

i==

=

=

+

11

relaia (1) devine:( )

2

1)1(

==+

nnmnnmm


6/30

6

Numrul cel mai mare de arce, cnd graful este complet, se obine atunci cnd nodurile sunt unite prin douarce, adic pentru nodurile x i y exist arcele (x,y) i (y,x), i este egal cu

( )( )1

21

2 =

nnnn

Lema Avem( )

2

1

3nn

grafuri complete cu n noduri.Definiie Ungraforientat esteturneu, dacoricare ar fi 2 vrfuri i i j, ij, ntre ele existun singur arc:arcul(i,j) sau arcul (j,i)Proprieti:

1. Orice graf turneu este graf complet.2. Avem

( )

2

1

2nn

grafuri turneu cu n noduri3. n orice graf turneu exist un drum elementar care trece prin toate vrfurile grafului.

Problem. Fiind dat un graf turneu, se cere s se afieze un drum elementar care trece prin toate vrfurile.#include#includeint s[20],a[20][20],n,L,i,j;void afisare_drum(){int i; cout


7/30

7

6. Conexitate

n aceast seciune, vor fi prezentate noiunile:- lan- drum- circuit- graf conex- component conex

Lan

Definiie. Fie G=(V, U) un graf orientat. Se numete lan, n graful G, o succesiune de arce, notat

kiiiuuuL ,...,,

21= cu proprietatea ca oricare dou arce consecutive au o extremitate comun (nu are

importan orientarea arcelor).Se ntlnesc noiunile:- extremitile lanului

fiind dat lanulkiii

uuuL ,...,,21

= se numesc extremiti ale sale extremitatea arcului ui1 care nu este

comun cu arcul ui2i extremitatea arcului uik care nu este comun cu arcul uik-1- lungimea lanului

fiind dat lanulkiii

uuuL ,...,,21

= prin lungimea sa se nelege numrul de arce care apar n L;

Exemplu de lan:cu reprezentarea grafic astfel:Fie graful G=(V, U), unde: V={1,2,3,4,5}

U={(1,3),(1,4), (2,3), (2,4), (5,2)}={ u1, u2, u3, u4, u5 }

1

L1=[ u1 ,u3 ,u5] este, n graful G, lan cu lungimea 3 i extremitile 1 i 5.L2=[ u1 ,u2, u4, u5] este, n graful G, lan cu lungimea 4 i extremitile 3 i 5.

Atenie! Dackiii

uuuL ,...,,21

= este lan n graful G, atunci i11

,...,,1 iii uuuL kk = este lan n graful G.

Drum

Definiie.Fie G=(V, U) un graf orientat. Se numetedrum, n graful G, o succesiune de noduri, notat

kiiixxxD ,...,,

21= , cu proprietatea Uxxxx

kk iiii

,,...,,

121(altfel spus

kk iiiixxxx ,,...,,

121 sunt arce).

Se ntlnesc noiunile:- extremitile drumului

fiind dat drumul kiii xxxD ,...,, 21= se numesc extremiti ale sale nodurile xi1 i xik (xi1 extremitate iniiali xik extremitate final)- lungimea drumului fiind dat drumul

kiiixxxD ,...,,

21= , prin lungimea sa senelege numrul de arce care apar n cadrul

su;Exemplu de drum:Fie graful G=(V, U) unde:V={ 1,2,3,4,5 }U={(1,3), (4,1), (3,2), (2,4), (5,2)}cu reprezentarea grafic astfel:


8/30

8

D1=(1, 3, 2) este, n graful G, drum cu lungimea 2 i extremitile 1 i 2.D2=(4, 1, 3, 2) este, n graful G, drum cu lungimea 3 i extremitile 4 i 2.Atenie! Dac

kiiixxxD ,...,,

21= este drum, n graful G, atunci nu neaprat i

1,...,,1 1 iiki xxxD k = este drum,

n graful G.

Definiie. Fie G=(V,U) un graf orientat. Se numetedrum elementar, n graful G, drumul

kiiixxxD ,...,,

21= cu proprietatea coricare dounoduri ale sale sunt distincte (altfel spus, printr-un nod

nu se trece dect o singurdat).

Exemplu: n graful de mai jos,1

3

drumul D1=(4, 1, 3, 2) este drum elementar.

Definiie. Fie G=(V, U) un graf orientat: Se numete drum neelementar, n graful G, drumul

kiiixxxD ,...,,

21= cu proprietatea c nodurile sale nu sunt distincte dou cte dou (altfel spus, prin anumite

noduri s-a trecut de mai multe ori).Exemplu: n graful de mai jos,

1

drumul D2=(4, 1, 3, 2, 4, 5, 2) este drum neelementar (prin 4 (i 2) s-a trecut de dou ori).

Circuit

Definiie: Fie G=(V, I) un graf neorientat. Se numete circuit, n graful G, drumulkiii

xxxD ,...,,21

= cu

proprietatea c xi1 = xiki are arcele cel compun diferite dou cte dou (circuitul se noteaz n continuare cuC).Exemplu: n graful de mai jos,

1

3drumul C=(1, 3, 2, 4, 1) este circuit.Definiie. Fie G=(V, U) un graf orientat. Se numete circuit elementar, n graful G, un circuit cuproprietatea c oricare dou noduri ale sale, cu excepia primului i a ultimului, sunt distincte.Exemplu: n graful de mai jos,

1

3

circuitul C=(1, 3, 2, 4, 1) este circuit elementar.


9/30

9

Definiie. Fie G=(V, U) un graf orientat. Se numete circuit neelementar, n graful G, un circuit cuproprietatea c nodurile sale, cu excepia primului i a ultimului, nu sunt distincte.Exemplu: n graful de mai jos

1

circuitul C=(1, 3, 4, 2, 5, 4, 1) este circuit neelementar (prin 4 s-a trecut de dou ori).

Graf conex

Definiie. Fie G=(V, U) un graf orientat. Graful G se numete conex dac pentru oricare dou vrfuri x i y,x#y, exist un lan de extremiti x i y.Exemplu de graf care este conex:

3Graful este conex, deoarece oricare ar fi vrfurile x i y, x#y, exist un lan in G care s le lege.

Exemplu de graf care nu este conex:1

2Graful nu este conex, deoarece exist dou vrfuri, cum ar fi 1 i 4, pentru care nu exist nici un lan n grafcare s le lege.

Component conex

Definiie. Fie G=(V, U) un graf orientat. Se numete component conex un graf orientat G1=(V1 ,U1) careverific urmtoarele condiii:- este subgraf al grafului G;- este conex;- nu exist nici un lan n G care s lege un nod din V, cu an nod din V-V1.Exemplu: Fie graful G=(V, U) : V={1,2,3,4,5} i U={(1,2), (3,1), (3,2), (4,5)}

1

2

Pentru graful de mai sus, graful G1=(V1,U1) unde: V1={4,5} i U1={(4,5)} este component conex,deoarece:- este subgraf al grafului G;- este conex;- nu exist nici un lan n G care s lege un nod din V, cu un nod din V-V1={1,2,3}La fel, se poate spune i despre graful G2=(V2,U2) unde: V2={1,2,3) i U2={(1,2)> (3,1), (3,2)}n concluzie, graful din figura de mai sus este format din dou componente conexe.Observaie. Fie G=(V, U) un graf orientat. Graful G este conex daci numai dac este format dintr-osingur component conex.Exemplu de graf conex (este format dintr-o singur component conex):


10/30

10

7. Reprezentarea grafurilor orientate

Fie G=(V, U) un graf orientat, unde V={x1, x2,..., xn} i U={u1, u2,..., um} . Deoarece ntre mulimea {x1,x2,..., xn} i mulimea {1, 2,..., n} exist o bijecie, xii, putem presupune, fr a restrnge generalitatea,mai ales pentru a uura scrierea, c V={1, 2,..., n}.n baza celor spuse mai sus, mai departe, n loc de xi vom scrie i, i n loc de arcul (xi ,xj) vom scrie (i ,j).Pentru a putea prelucra un graf orientat cu ajutorul unui program, trebuie mai nti s fie reprezentat nprogramul respectiv.

Pentru a reprezenta un graf orientat, ntr-un program, exist mai multe modaliti folosind diverse structuride date; dintre acestea n continuare vom prezenta:- reprezentarea prin matricea de adiacen;- reprezentarea prin matricea vrfuri-arce;- reprezentarea prin matricea drumurilor;- reprezentarea prin listele de adiacen;- reprezentarea prin irul arcelor.

Matricea de adiacen

Fie G=(V; U) un graf orientat cu n vrfuri (V={ 1,2, ..., n}) i m arce.Matricea de adiacen (AMn({0,1})), asociat grafului G, este o matrice ptratic de ordin n, cu

elementele:( )

( )

=

Ujidaca

Ujidacaa

ji,,0

,,1,

(altfel spus, ai,j=1, dac exist arc ntre i i j i ai,j=0 dac nu exist arc ntre i i j.Exemplul 1.Fie graful reprezentat ca n figura de mai jos:

1

2 3Matricea de adiacen asociat grafului este:

=

=

0001

0000

1100

0100

44434241

34333231

24232221

14131211

aaaa

aaaa

aaaa

aaaa

A

Exemplul 2.Fie graful reprezentat ca n figura de mai jos:

1

2 3Matricea de adiacen asociat grafului este:

=

=

0010

1001

0100

1010

44434241

34333231

24232221

14131211

aaaa

aaaa

aaaa

aaaa

A

* Comentarii:l. Matricea de adiacen este o matrice ptratic, de ordin n, i nu este neaprat simetric fa de diagonalaprincipal, aa cum este n cazul grafurilor neorientate.Secvenele de citire a matricei de adiacen:

int a[100][100];.................coutn;for (i=1;i


11/30

11

a[x][y]=1;}....................

2. Matricea de adiacen are toate elementele de pe diagonala principal egale cu 0 (ne referim la definiia 1,cnd graful nu are bucle).

3. Numrul elementelor egale cu 1 de pe linia i este egal cu gradul exterior al vrfului i.int gr_ext(int i){int j , s;s=0;

for (j=1;j


12/30

12

Exemplul 2 . Fie graful G :V={ 1,2,3,4},U={(1,2),(1,4),(2,3),(3,1),(3,4),(4,2)}=

{u1, u2, u3, u4,u5, u6},reprezentat ca n figura de mai jos:

1

3Matricea vrfuri-arce asociat grafului este:

=

=

110010

011100

100101

001011

464544434241

363534333231

262524232221

161514131211

bbbbbb

bbbbbb

bbbbbb

bbbbbb

B

Comentarii:1. Matricea vrfuri-arce nu este neaprat o matrice ptratic.

#Secvenele de citire a matricei vrfuri-arce:int b[100][100];.........................cout


13/30

13

5. Pe fiecare coloan j, exist un singur, element egal cu 1 i un singur element egal cu -1.Indicele liniei pe care se afl 1 este extremitatea iniial a arcului u;Indicele liniei pe care se afl -1 este extremitatea final a arcului u,

Construirea matricei de adiacen, cnd se cunoate matricea vfuri-arce.- se parcurge matricea vrfuri-arce, de la prima pn la ultima coloan, cu j- pe coloana j, se depisteaz indicele liniei pe care se afl 1. fie acesta plus l;- pe coloana j, se depisteaz indicele liniei pe care se afl -I, fie acesta minus l;- n matricea de adiacen elementul a[plus l, minus l] se face 1.

for (j=1 j


14/30

14

=

=

0101

0000

1101

0100

44434241

34333231

24232221

14131211

dddd

dddd

dddd

dddd

D

Exemplul 2 .Fie graful G : V={1,2,3,4},U={(1,2),(1,4),(2,3),(3,1),(3,4),(4,2)}=

{u1, u2, u3, u4, u5, u6}reprezentat ca n figura de mai jos:

1

3

Matricea drumurilor asociat grafului este:

=

=

0111

1111

1111

1111

44434241

34333231

24232221

14131211

dddd

dddd

dddd

dddd

D

Comentarii:1. Matricea drumurilor este o matrice ptratic.

n continuare, este prezentat n pseudocod algoritmul Roy-Warshall de determinare a matricei drumurilorplecnd de la matricea de adiacen. Algoritmul const ntr-un ir de transformri aplicate matricei deadiacen. Vom spune c exist drum de la nodul i la nodul j, dac gsim un nod k cu proprietatea c existdrum de la i la k i drum de la k la j. Astfel:Un element ai,j care este 0 devine1, dac exist un nod k a.. ai,k=1 i ak,j=1. Pentru a gsi toate arcelenodului k trebuie parcurse pe rnd n variabila k toate nodurile 1,2,.., n.

...............pentru k=1 ... n

pentru i=1 ... n (i#k)pentru j = 1 ... n (j#k)

dac ai,j=0 si i!=k si j!=k atunciai,j= aik * akj

.....................

2. Dac n matricea drumurilor dii=1, nseamn c exist n graf un circuit de extremiti i.3. Dac n matricea drumurilor linia i i coloana i au elementele egale cu 0, nodul i este un nod izolat.

*Programul C/C++ de construirei afiare a matricei drumurilor.#include #include #include typedef int mat[30][30];mat a;int i, j, k, n, m, x, y;

void main(){clrscr();coutn;coutm; secvena de citire afor (i=1;i


15/30

15

if (a[i][j]==0)a[i][j]=a[i][k] *a[k][j];

cout


16/30

16

T2,1=5, pentru c primul vecin (3) al lui 1 s-a trecut la coloana 5 (T1,5=3);T2,5=6, pentru c urmtorul vecin (4) al lui 1 s-a trecut la coloana 6 (T1,6=4);T2,6=0, pentru c vecinul T1,6 (4) al lui 1 este ultimul din list.A treia etap. Se trec n tabel vecinii lui 2, ncepnd de la coloana 7.

1 2 3 4 5 6 7 81 2 3 4 3 4 35 7 6 0 0

T2,2=7, pentru c primul vecin (3) al lui 2 s-a trecut la coloana 7 (T1,7=3);T2,7=0, pentru c vecinul T1,7 (3) al lui 2 este ultimul din list.

A patra etap. Se trec n tabel vecinii lui 3, ncepnd de la coloana 8.1 2 3 4 5 6 7 81 2 3 4 3 4 35 7 0 6 0 0

T2,3=0, pentru c 3 nu are succesori, deci lista sa este vidUltima etap. Se trec n tabel vecinii lui 4, ncepnd de la coloana 8 (aici s-a ajuns)

1 2 3 4 5 6 7 81 2 3 4 3 4 3 25 7 0 8 6 0 0 0

T2,4=8, pentru c primul vecin (2) al lui 4 s-a trecut la coloana 8 (T1,8= 2);T2,8=0, pentru c vecinul T1,8 (2) al lui 4 este ultimul din list.

2. Se folosete un tablou unidimensional, cu numele cap, i un tablou bidimensional, cu numele L (carereine listele succesorilor pentru fiecare nod), caracterizate astfel:Tabloul cap:- are n componente;- capi= c, dac primul nod din lista vecinilor lui i este trecut n tabloul L la coloana c, adic L1,c este

primul vecin al lui i,i capi =0, dac nodul i nu are succesori.Tabloul L:- are m componente;- dac k este un vecin al nodului i, atunci:

L1,p =k i L2,p=0, dac k este ultimul vecin din list, sau

L1,p=k i L2,p=p+1, dac k nu este ultimul vecin din list.(p este coloana la care s-a ajuns n tabloul L)Exemplu de completare a tablourilor cap i L, pentru graful de la exemplul lTabloul cap

1 2 3 41 3 0 4

Tabloul L

1 2 3 43 4 3 22 0 0 0

3. Se folosete un tablou bidimensional, cu numele L, caracterizat astfel:- are n linii;- pe linia i; se trec succesorii nodului i.Exemplu de completare a tabloului L, pentru graful:Tabloul L

3

1 4

2

1 3


17/30

17

Implementarea n limbajul C++, a ideii prezentate mai sus, se realizeaz conform secvenei deprogram prezentat mai jos.

....................int L[20][20];int nr_vec[20];coutn;for (i=1;i


18/30

18

- deci, U={( el[1],e2[1]) , (el[2],e2[2]) ,..., ( el [m],e2[m])}

Secvena C++corespunztoare este:int el[100], e2[100];int n, m, i;coutn;coutm;for (i=1;i


19/30

19

if (a[i][j]==1){ k=k+1;u[k].x=i;u[k].y =j;}

m=k;..................

8. Graf tare conex. Componente tare conexe

n aceast seciune, vor fi prezentate noiunile:- graf tare conex- component tare conex- algoritmul de descompunere a unui graf n componente tare conexe

Graf tare conex

Definiie. Fie G=(V, U) un graf orientat. Graful G se numete tare conex, dac pentru oricare dou vrfurix i y exist un drum n G de la x la y i un drum de la y la x. Exemplu de graf tare conex.

1

Graful este tare conex, deoarece, oricare ar fi vrfurile x i y, exist un drum in G de la x la y i un drum dela y la x.

Component tare conex

Definiie. Fie G=(V, U) un graf orientat. Se numete component tare conex, un graf orientat G1 =(V1, U1)care verific urmtoarele condiii:

- este subgraf al grafului G- este tare conex;- oricareare fi xV-V1, subgraful lui G generat de V1U{x} nu mai este tare conex . Exemplu. Fie graful orientat prezentat n figura de mai jos:

1

3

Acest graf are dou componente tare conexe:- subgraful generat de nodurile 1, 2, 3;- subgraful generat de nodurile 4, 5, 6.Observaie. Fie G=(V, U) un graf orientat: Graful G este tare conex, dac admite o singur component tareconex.

Algoritmul de descompunere a unui graf n componente tare conexe

Algoritmul procedeaz astfel:- la nceput, nu este depistat nici o component tare conex ( nc=0);- deci, nici un nod nu face parte din vreo component tare conex (luate=[ ]);- se parcurg nodurile grafului, cu i;

- dac i nu a fost introdus n nici o component tare conex,


20/30

20

- se mrete numrul componentelor tare conexe cu 1,- se construiete noua component tare conex, astfel:

- se intersecteaz predecesorii lui i cu succesorii si, i se reunesc cu {i}.

Pentru implementarea acestui algoritm, n limbajul C++, cu ajutorul programului prezentat mai jos, s-aufolosit:Funciile:Succesori(i, S):care pune n irul S toate nodurile j, din graf , cu proprietatea c exist drum ntre i i ele.Predecesori(i, P):care pune n irul P toate nodurile j, din graf, cu proprietatea c exist drum ntre ele i i.

Vectorul:Comp :ale crui componente, care sunt iruri de elemente, vor reine, la final, componentele tare conexe;Variabilele:d : matricea drumurilor;luate : un ir care reine toate nodurile care fac deja parte dintr-o component tare conex;nc : reprezint numrul componentelor tare conexe depistate;n program, au mai fost folosite i alte variabile dar deoarece rolul lor reiese foarte uor din urmrireaprogramului nu-l mai comentm.

#include #include #include

typedef int mat[20][20];typedef int sir[20];mat d;sir S, P, luate;sir comp[50], ncomp;int ok,nl, i, j, n, m, nc, ns, np;void succesori(int i, sir S, int& ns){int j;ns=0;for (j=1;j


21/30

21

}void main(){clrscr();coutn;for (i=1;i


22/30

22

( )

==

Ujisijidaca

jidaca

ttulcuarcunexistajsiiredacat

cji

,,

,0

coscosint,cos

,

n cazul problemelor de maxim, fiind dat graful G=(V, U) i se asociaz matricea costurilor, forma 2, definitastfel:CMn (R), unde:

( )

==

Ujisijidaca

jidaca

ttulcuarcunexistajsiiredacat

cji

,,

,0

coscosint,cos

,

Exemplu: Fiind dat graful din figura de mai jos (costul fiecrui arc fiind scris pe ea)1 13

3matricea costurilor se scrie in felul urmtor:Forma 1:

=

=

014

0

1215013110

44434241

34333231

24232221

14131211

cccc

cccc

cccc

cccc

C

Forma 2:

=

=

014

0

12150

13110

44434241

34333231

24232221

14131211

cccc

cccc

cccc

cccc

C

Observaii.1. Matricea costurilor forma 1 difer de matricea costurilor forma 2 prin faptul c n loc de apare -.2: n program nu se poate scrie sau -, de aceea recomandm ca atunci cnd trebuie folosite s sedefineasc dou constante foarte mari, ca de exemplu, pentru : const p infinit = 1.e10;

pentru - : const m infinit=-1.e10;n continuare, vor fi prezentai doi algoritmi care permit rezolvarea unor probleme de minim (maxim), ianume, vor fi prezentai:algoritmul Roy-Floyd i algoritmul lui Dijkstra..

Algoritmul Roy-Floyd

Acest algoritm se aplic n cazul problemelor n care se d un graf G=(V, U), care are matricea costurilor C,i se cere s se determine lungimea drumurilor minime, i n unele cazuri i nodurile care constituiedrumurile respective, ntre oricare dou noduri ale grafului.Observaie. Algoritmul are la baz urmtoarea idee:

"Dac drumul minim de la nodul i la nodul j trece prin nodul k, atunci i drumul de nodul i lanodul k, precum i de la nodul k la nodul j, este minim"

i const, de fapt, ntr-un ir de n transformri aplicate matricei costurilor C, astfel:Tk(C)=B , BMn (R), bi,j=minim(ci,j,ci,k+ck,j),i,j {1,..n}care se poate implementa astfel:

for k=1 ... nfor i=1 ... n

for j=l ... nif (c[i,j]


23/30

23

Descrierea detaliat a algoritmului prezentat mai sus:Pentru fiecare pereche de noduri (i,j), unde i,j { 1,...,n}, se procedeaz astfel:

se parcurg cu k toate nodurile grafului, diferite de i i j,pentru fiecare nod k, se execut:

dac costul drumului ntre nodurile i i j este mai mic dect suma costurilor drumurilorntre nodurile i i k i ntre nodurile k i j, atunci costul drumului iniial de la i la j se vanlocui cu costul drumului i-k-j, evident, acest lucru fcndu-se prin modificareamatricei costurilor.

Observaie. Algoritmul prezentat n forma de mai sus, permite dect calcularea lungimii drumurilor minimentre oricare dou noduri ale grafului. Dac se dorete i afiarea nodurilor care compun efectiv acestedrumuri, va trebui completat astfel:Dac lungimea drumului miinim dintre nodurile i i j este egal cu suma dintre lungimile a 2 drumuri caretrec printr-un nod intremediar k atunci nodul k face parte din drumul de lungime minim de la i la j#include#include#includeint a[50][50],n,i,j,c,k,gasit=0,x,y;int const p_inf=10000;ifstream f("rf.in");void init() //se initializeaza matr costurilor

{f>>n;for(i=1;ii>>j>>c) a[i][j]=c;f.close();}void transformare() //se transforma matriceacosturilor{for(k=1;k


24/30

24

for (k=1;k


25/30

25

for (i=1;i>y>>val;c[x][y]=val;}

for (i=1;i


26/30


27/30

27

p 0 0 1 0 0 1

Pasul 2

Dintre nodurile nealese nc, nealese={2,3,4,5,6}, se alege nodul j pentru care dj=min{d2, d3, d4, d5, d6};deci, se alege j=3, pentru ca d3 =min{, 2, , , 2}

1 2 3 4 5 6d 0 2p 0 1

Se completeaz componentele vectorilor d i p, pentru nodurile nealese, astfel:2 : min(d2, d3+C3,2)=min(,2+)= (d2i p2 rmn nemodificate)4 : min(d4, d3+C3,4)=min(,2+)= (d4i p4 rmn nemodificate)5 : min(d5, d3+C3,5)=min(,2+)= (d5i p5 rmn nemodificate)6 : min(d6, d3+C3,6)=min(2,2+2)=2 (d5i p5 rmn nemodificate)

1 2 3 4 5 6d 0 2 2p 0 0 1 0 0 1

Pasul 3

Dintre nodurile nealese nc, nealese={2,4,5,6}, se alege nodul j pentru care dj=min{d2, d4, d5, d6}; deci, sealege j=6, pentru c d6 =min{, , , 2}

1 2 3 4 5 6d 0 2 2p 0 1 1

Se completeaz componentele vectorilor d i p, pentru nodurile nealese, astfel:2 : min(d2, d6+C6,2)=min(,2+)= (d2i p2 rmn nemodificate)4 : min(d4, d6+C6,4) =min(,2+2)=4 (d4=4 i p4=6)5 : min(d5, d6+C6,5)=min(,2+3)=5 (d5=5 i p5=6)

1 2 3 4 5 6d 0 2 4 5 2p 0 0 1 6 6 1

Pasul 4

Dintre nodurile nealese nc, nealese={2,4,5}, se alege nodul j pentru care dj=min{d2, d4, d5}; deci, se alegej=4, pentru c d min{, 4, 5}

1 2 3 4 5 6d 0 2 4 2p 0 1 6 1

Se completeaz componentele vectorilor d i p, pentru nodurile nealese, astfel:

2 : min(d2, d4+C4,2)=min(,4+3)=7 (d2 =7 i p2 =4)5 : min(d5, d4+C4,5)=min(5,4+)=5 (d5i p5 rmn nemodificate)

1 2 3 4 5 6d 0 7 2 4 5 2p 0 4 1 6 6 1

Pasul 5Dintre nodurile nealese nc, nealese={2,5}, se alege nodul j pentru care dj=min{d2, d5}; deci, se alege j=5,pentru ca d5 =min{, 5}.


28/30

28

1 2 3 4 5 6

d 0 2 4 5 2p 0 1 6 6 1

Se completeaz componentele vectorilor d i p, pentru nodurile nealese, astfel:2 : min(d2, d5+C5,2)=min(7,S+)=7 (d2i p2 rmn nemodificate)

1 2 3 4 5 6

d 0 7 2 4 5 2p 0 4 1 6 6 1

Concluzii:Drumurile minime de la nodul 1 la celelalte noduri sunt:2 : p2=4, p4=6, p6=1; deci, de la 1 la 2 avem : 1, 6, 4, 23 : p3=1; deci, de la 1 la 3 avem : 1, 34 : p4 =6, p6 =1; deci, de la 1 la 4 avem : 1, 6,45 : p5=6, p6=1; deci, de la 1 la 5 avem : 1, 6, 56.1 p6 =1; deci, de la 1 la 6 avem : 1, 6

#include#include#includeifstream f("d.in");const p_inf=10000;float a[50][50],d[50],min;int n,i,j,pl,poz,p[50],s[50],c;void drum (int i){if(p[i]!=0) drum(p[i]);coutj>>c)a[i][j]=c;f.close();coutpl;for(i=1;i


29/30

29

{d[j]=d[poz]+a[poz][j];p[j]=poz;}}for(i=1;i


30/30

if(p[i]!=0){cout

Date post:	07-Apr-2018
Category:	Documents
Upload:	liana-popovici
View:	218 times
Download:	0 times

Grafuri+Orientate

Documents