1

II GRAFURI TARE CONEXE

DRUMURI HAMILTONIENE

DISTANTE MINIME

ALGORITMI MATRICEALI

Daca notiunea de conexitate intr-un graf orientat este

definita cu ajutorul conceptului de lant, notiunea de tare

conexitate se va defini cu ajutorul conceptului de drum.

Definitia 1 Un graf G = (V,U) se numeste tare conex

daca are proprietatea ca pentru oricare doua varfuri distincte

x,y exista un drum de la x la y si un drum de la y la x.

Altfel zis, oricare doua varfuri din graful orientat sa se

afle pe un circuit.

Matricea drumurilor unui graf tare conex are toate

elementele egale cu unu.

Definitia 2 Se numeste componenta tare conexa a

unui graf orientat G = (V,U), un subgraf G'=(V',U') cu

proprietatea ca este tare conex si maximal in raport cu aceasta

proprietate, adica ∀z∈V\V' subgraful lui G generat de V'∪{z}

nu mai este tare conex.

Fie R o relatie binara definita pe multimea V a grafului

orientat G = (V,U), astfel: xRy daca x=y sau exista un drum

2

de la x la y si un drum de la y la x. Aceasta relatie este o

relatie de echivalenta (Exercitiu!).

Clasele de echivalenta corespunzatoare relatiei R sunt

componentele tare conexe ale lui G.

Exemplul 1 Sa consideram urmatorul graf orientat G

care nu este tare conex.

2 4

6

1

3 5

Fig.1

Componentele tare conexe sunt: C1={1,2,3,4};C2={5};

C3={6}.

Propozitia 1 Fie C1 si C2 doua componente tare

conexe distincte si varfurile x,y din C1, x',y' din C2. Daca exista

un drum dx,x', atunci nu va mai exista un drum dy

',y.

3

Demonstratie: Sa presupunem ca ar exista un drum

dy',y in graf. Atunci, conform ipotezei, vor exista drumurile

dx,x',y

' si dy,'y,x. Prin urmare, varfurile x si y' s-ar gasi pe un

circuit (contradictie!).

Descrierea unui algoritm matriceal pentru identificarea

componentelor tare conexe

Pentru determinarea componentelor tare conexe

intr-un graf orientat G=(V,U), se poate utiliza matricea

drumurilor asociata grafului. Daca matricea D are toate

elementele de pe diagonala principala egale cu 1, atunci toate

varfurile lui G se afla in circuite. Sa notam cu S(xj) multimea

varfurilor lui G care sunt extremitati finale ale unor drumuri

care pleaca din xj, iar cu P(xj) multimea tuturor varfurilor din

G care sunt extremitati initiale ale unor drumuri care sosesc in

varful xj.

Se observa ca multimea S(xj) consta din acele varfuri

xk cu proprietatea d[xj,x k] =1, adica varfurile corespunzatoare

coloanelor din matricea D care contin elemente egale cu unu

pe linia j. Analog, multimea P(xj) consta din acele varfuri x k

cu proprietatea ca d[xk,xj] = 1, adica varfurile corespunzatoare

liniilor din D care contin elemente egale cu unu pe coloana j.

Componenta tare conexa corespunzatoare varfului xj

va fi (S(xj)∩P(xj)) ∪{xj}.

4

Matrice latine. Drumuri hamiltoniene

A. Kaufmann si J. Malgrange au introdus in calculul

operational conceptul de matrice latina. Matricele latine

participa la relatia de definire a unui graf. Secvente de varfuri

ale unui graf orientat pot fi caracterizate de anumite

proprietati.

Definitia 3 Varfurile unui graf orientat care au

aceeasi proprietate P si care se succed intr-o anumita ordine

compatibila cu ordinea din graf se numeste secventa.

Operatia ce se poate realiza cu secventele, care au

aceeasi proprietate P, este concatenarea.

Prin concatenarea a doua secvente, cu aceeasi

proprietate P, nm jjjiii xxxsxxxs ,...,,,,...,,

2121 21 == , se

obtine secventa nm jjjiii xxxxxxss ,...,,,,...,,*

322121 = , daca

au loc urmatoarele doua conditii:

1) 1ji xx

m=

2) s1*s2 are proprietatea P.

Daca una din cele doua conditii nu este indeplinita,

atunci se va considera s1*s2 = φ .

Conventii: .*;*;* φφφφφφφ === ss

Exemplul 2 Se considera urmatorul graf orientat:

5

1

2 5

3 4

Fig. 2

Proprietatea P consta in faptul ca varfurile din

secvente se afla pe drumuri elementare.

Fie secventele:

s1= 2 5 3

s2= 2 1 4

s3= 3 2 1 4

s4=3 1 4.

Se observa ca:

s1*s2=φ (nu are loc conditia 1)

s1*s3= φ (drumul (2 5 3 2 1 4) nu este elementar)

s1*s4= (2 5 3 1 4).

Concatenarea este o operatie asociativa, dar nu este

6

comutativa.

Tranzitiile din graf se vor dispune sub forma unui

tablou (matrice latina).

A(0) 1 2 3 4 5

1 1,4 1,5

2 2,1 2,5

3 3,1 3,2

4 4,1 4,2 4,3

5 5,3

Vom construi matricea A(1) pornind de la matricea A(0)

luand secventele fara primul element al lor tinand cont de

definitia concatenarii.

A(1) 1 2 3 4 5

1 4 5

2 1 5

3 1 2

4 1 2 3

5 3

Concatenarea celor doua tablouri se realizeaza similar

7

produsului a doua matrice prin tehnica " linie-coloana",

astfel:

A(2) 1 2 3 4 5

1 - 142

143

153 φ φ

2 φ - 253 214 215

3 321 φ - 314 315

325

4 421

431

432 φ - 415

425

5 531 532 φ φ -

Exemplu de calcul: Linia 1 din A(0) "inmultita" cu

coloana 1 din A(1) va conduce la secventa 1 4 1 care este un

circuit de lungime 2 si nu ne intereseaza de aceea am trecut (-).

In rest se obtin numai secvente vide (φ ).

La acest pas, se vor obtine toate drumurile elementare

de lungime 2.

In continuare, se va efectua operatia intre A(2) si A(1)

pentru a obtine A(3) ce va indica drumurile elementare de

lungime 3.

8

A(3) 1 2 3 4 5

1

-

1432

1532 φ φ 1425

2 2531 - 2143

2153 φ φ

3 φ 3142 - 3214 3215

4 4321 φ 4153

4253

- 4215

4315

4325

5 5321 φ φ 5314 -

Drumurile elementare de lungime 4, le vom intalni ca

elemente in tabloul A(4).

Pentru a calcula pe A(4) vom opera cu tablourile A(3) si

A(1).

A(4) 1 2 3 4 5

1 - φ 14253 φ 14325

2 φ - φ 25314 φ

3 φ φ - φ 31425

4 42531 41532 42153 - 43215

5 φ 53142 φ 53214 -

9

A(5) 1 2 3 4 5

1 - φ φ φ φ

2 φ - φ φ φ

3 φ φ - φ φ

4 φ φ φ - φ

5 φ φ φ φ -

In tabloul A(5) ar trebui sa se identifice drumurile

elementare de lungime 5. Se observa ca nu exista drumuri

elementare de lungime 5.

Prin urmare, exista drumuri hamiltoniene in graf (vezi

A(4)).

Reluati calculele si identificati circuitul hamiltonian

din graful considerat.

Algoritmi pentru calculul distantelor minime

Fie G = (V,U) un graf orientat si λ : U → R+ o

functie care asociaza fiecarui arc din G un numar real

nenegativ numit lungimea sa. In cazul de fata, prin lungimea

unui drum din G se intelege suma lungimilor arcelor sale, iar

distanta minima dintre doua varfuri oarecare ale lui G consta

in lungimea drumurilor scurte care au ca extremitati aceste

varfuri.

10

Algoritmul lui Roy-Floyd

Fie G = (V,U) un graf orientat cu V = {x1,x2,…,xn},

etichetat. Vom defini matricea distantelor directe ale lui G ca

fiind matricea A(nxn) unde:

∉∞=

∈

=Uxxdaca

jidacaUxxdacax

jia

ji

jij

),(0

),()),((x

],[iλ

(1≤ i,j ≤ n)

Fie A*(nxn) matricea distantelor minime dintre

varfurile grafului orientat G care se defineste astfel:

∞

==

altfeljia ji,

* minjidaca0

],[ (1≤i,j ≤ n)

unde mini,j reprezinta minimul dintre lungimile drumurilor cu

extremitatile i, j.

Rolul acestui algoritm este de a gasi matricea

distantelor minime A* pornind de la matricea distantelor

directe A.

for k=1 , n

for i =1 , n

if (i≠k)

for j = 1 , n

if (j≠i ∧ j≠k)

a[i,j] = min (a[i,j] , a[i,k]+a[k,j] )

11

Ciclurile for(i), for(j), vor recalcula elementele cu

indici diferiti intre ei ale unei submatrice cu n-1 linii si n-1

coloane, deci este necesar un numar de (n-1)2 –(n-1) = (n-1)*

(n-2) operatii de adunare, respectiv comparatii. Intregul

algoritm (incluzand for(k)) va necesita un numar de

n(n-1)(n-2) operatii de adunare si tot atatea comparatii , adica

O(n3 ).

Observatie: Algoritmul respectiv se poate trata si in

limbaj operatorial .

Tk(A(k-1))=A(k) (k=1,n) unde,

≤≤===

≠≠+= −

−−−

),1(,0),,(

)},,(),(),,(min{),( )1(

)1()1()1(

)(

njijidacakjsaukidacajiA

kjijkAkiAjiAjiA k

kkk

k

Asadar, la aplicarea operatorului Tk, linia si coloana k

din matricea A(k) raman nemodificate, adica identice cu cele

din matricea A(k-1).

Elementele de pe diagonala principala a matricei A

sunt egale cu zero.

Acest algoritm, putin modificat, poate servi la

determinarea drumurilor de lungime minima dintre varfurile

grafului orientat G.

Vom defini o matrice D(nxn) ale carei elemente

reprezinta submultimi de varfuri ale lui G.

Initializarea matricei D va fi de forma urmatoare:

12

∞=∞<

=],[

],[}{x],[ i

jiadacajiadaca

jidφ

(1≤i,j ≤ n)

Elementul d[i,j] reprezinta submultimea varfurilor

vecine varfului xj aflate pe drumuri de la xi la xj. In ciclurile

dupa i si j, elementele d[i,j] se reactualizeaza astfel:

+>+=∪

+<=

j]a[k,k]a[i,j]a[i,dacaj]d[k,j]a[k,k]a[i,j]a[i,dacaj]d[k,j]d[i,

j]a[k,k]a[i,j]a[i,dacaj]d[i,],[ jid

(1≤i , j , k ≤ n)

Cunoscand varfurile vecine (in sens invers orientarii

drumului) pentru orice drum de lungime minima din graf,

acesta se poate reconstitui usor.

Exemplul 4 Sa consideram urmatorul graf:

2 2 3

1 2

4 5

1 8 5 4

5 3

6 1 5

Fig. 6

13

Vom calcula matricea distantelor minime A* si a

drumurilor minime D*.

A=A(0) 1 2 3 4 5 6

1 ∞ 1 4 ∞ ∞ ∞

2 ∞ 0 2 5 8 ∞

3 ∞ ∞ 0 2 5 ∞

4 ∞ ∞ ∞ 0 3 5

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

Matricea A=A(0)(matricea distantelor directe)

D(0) 1 2 3 4 5 6

1 x1 x1 x1

2 x2 x2 x2 x2

3 x3 x3 x3

4 x4 x4 x4

5 x5 x5

6 x6

Matricea initiala D(0)

Nota: casuta libera desemneaza faptul ca ea contine

multimea vida de varfuri.

14

Se va aplica operatorul T1 matricei A(0) . Deoarece

coloana 1 din matricea A(0) are toate elementele ∞ , A(1) =A(0),

D(1) = D(0).

Se aplica operatorul T2 matricei A(1) si se obtine:

A(2) 1 2 3 4 5 6

1 0 1 3 6 9 ∞

2 ∞ 0 2 5 8 ∞

3 ∞ ∞ 0 2 5 ∞

4 ∞ ∞ ∞ 0 3 5

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

Matricea A(2)

Pentru a calcula, de exemplu, elementul A(2)(1,3),

vom calcula min{ A(1)(1,3), A(1)(1,2)+A(1)(2,3)} (s-a aplicat

operatorul T2 , deci k=2). Linia si coloana 2 raman identice

cu cele din matricea A(1).

D(2) 1 2 3 4 5 6

1 x1 x1 x2 x2 x2

2 x2 x2 x2 x2

3 x3 x3 x3

4 x4 x4 x4

5 x5 x5

6 x6

15

Matricea D(2) se calculeaza prin actiunea operatorului

T2 asupra matricei A(1) si tinand seama de matricea D(1). De

exemplu, pentru a calcula elementul D(2)(1,3) se vor compara

elementele A(1)(1,3) cu elementul suma A(1)(1,2)+A(1)(2,3). Se

gaseste ca A(1)(1,3)> A(1)(1,2)+A(1)(2,3) (k=2). Prin urmare, se

va lua D(2)(1,3)=D(1)(2,3). Linia si coloana 2 din matricea D(2)

vor fi identice cu cele din matricea D(1). Diagonala principala,

evident, nu se va modifica.

Analog se vor calcula, in continuare, elementele

matricelor A(3),...,A(6), respectiv D(3),...,D(6).

A(3) 1 2 3 4 5 6

1 0 1 3 5 8 ∞2 ∞ 0 2 4 7 ∞3 ∞ ∞ 0 2 5 ∞4 ∞ ∞ ∞ 0 3 5

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

Matricea A(3). Se aplica operatorul T3(A(2)).D(3) 1 2 3 4 5 6

1 x1 x1 x2 x3 x3

2 x2 x2 x3 x3

3 x3 x3 x3

4 x4 x4 x4

5 x5 x5

6 x6

16

Matricea D(3)

(Se va tine seama de matricea T3(A(2)) si D(2))

A(4) 1 2 3 4 5 6

1 0 1 3 5 8 10

2 ∞ 0 2 4 7 9

3 ∞ ∞ 0 2 5 7

4 ∞ ∞ ∞ 0 3 5

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

Matricea A(4). Se aplica operatorul T4(A(3)).

D(4) 1 2 3 4 5 6

1 x1 x1 x2 x3 x3,x4 x4

2 x2 x2 x3 x3,x4 x4

3 x3 x3 x3,x4 x4

4 x4 x4 x4

5 x5 x5

6 x6

(Se va tine seama de matricea T4(A(3)) si D(3))

A(5) 1 2 3 4 5 6

1 0 1 3 5 8 9

2 ∞ 0 2 4 7 8

3 ∞ ∞ 0 2 5 6

4 ∞ ∞ ∞ 0 3 4

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

17

D(5) 1 2 3 4 5 6

1 x1 x1 x2 x3 x3,x4 x5

2 x2 x2 x3 x3,x4 x5

3 x3 x3 x3,x4 x5

4 x4 x4 x5

5 x5 x5

6 x6

Matricea D(5)

A(6) 1 2 3 4 5 6

1 0 1 3 5 8 9

2 ∞ 0 2 4 7 8

3 ∞ ∞ 0 2 5 6

4 ∞ ∞ ∞ 0 3 4

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

Matricea A(6). Se aplica operatorul T6(A(5))=A(5)=A*.

D(6) 1 2 3 4 5 6

1 x1 x1 x2 x3 x3,x4 x5

2 x2 x2 x3 x3,x4 x5

3 x3 x3 x3,x4 x5

4 x4 x4 x5

5 x5 x5

6 x6

Matricea D(6)=D*

18

Se gaseste distanta minima de la x1 la x6 ca fiind

a*[1,6] = 9 . Drumurile de lungime minima de la x1 la x6 se

observa din matricea D* astfel:

Elementul d*[1,6] = x5. Se cauta in prima linie si a 5-a

coloana si se gaseste d*[1,5] ={ x3,x4}, adica drumurile de

lungime minima de la x1 la x6 se vor termina prin succesiunile

x3,x5,x6, respectiv x4,x5,x6.

Pentru prima succesiune de varfuri cautam in prima

linie si a treia coloana si gasim x2, iar in coloana a doua se

gaseste x1. Asadar un drum de lungime minima de la x1 la x6

este (x1,x2,x3,x5,x6) . Procedand analog cu a doua succesiune, se

obtine al doilea drum minim (x1,x2,x3,x4,x5,x6). Fiecare din cele

doua drumuri au lungimea 9.

In algoritmul descris se observa ca, dupa etapa de

initializare ( )( 2nΘ ), se trece la recalcularea elementelor cu

indici diferiti intre ei pentru o submatrice de dimensiuni

(n-1)*(n-1). Este necesar un numar de (n-1)(n-2) operatii de

adunare, respectiv comparatii. In total se vor executa un numar

de n(n-1)(n-2) operatii de adunare si tot atatea comparatii.

Asadar, ordinul de complexitate al algoritmului este ).( 3nΘ

Algoritmul lui Yen

Acest algoritm este util in determinarea distantelor

minime a*[1,2], a*[1,3],...,a*[1,n] de la varful x1 la varfurile

x2, x3,…,xn ale grafului orientat G = (V,U).

19

Descrierea algoritmului

p1. Se determina in matricea distantelor directe A,

minimul dintre distantele directe a[1,2], a[1,3], …,a[1,n].

Daca acest minim se realizeaza, de exemplu, pentru un indice

i0, adica a[1,io] = min{a[1,k] / k = 2,3,…,n}, atunci

distanta minima este a*[1,i0] = a[1,io]. Este posibil ca indicele

i0 sa nu fie unic.

p2. Elementele din prima linie a matricei A se vor

transforma astfel:

Pentru orice i≠1, io, elementul a[1,i] se inlocuieste cu

min(a[1,i] , a[1,io]+a[io,i]). Din matricea obtinuta se suprima

linia si coloana de rang io, conservand rangurile initiale din

matricea A, pentru liniile si coloanele ramase.

Daca matricea obtinuta este de ordinul 2, atunci

elementul a[1,2] din aceasta matrice reprezinta distanta

minima de la varful x1 la varful xk unde k este rangul initial al

coloanei a doua din matricea curenta. In aceasta situatie

algoritmul se opreste deoarece au fost determinate distantele

minime a*[1,2] , a*[1,3] ,…,a*[1,n].

In caz contrar, se va trece la primul pas, efectuandu-se

aceleasi operatii asupra matricei curente ca si asupra lui A

initial. In acest moment un element a[1,i] va fi elementul din

prima linie si coloana i a matricei obtinute, pentru care s-au

conservat rangurile initiale ale liniilor si coloanelor matricei A.

Complexitatea algoritmului va fi determinata de

20

numarul operatiilor de adunare si comparare folosite de

algoritm.

La pasul p1 sunt necesare cel mult n-2 comparari,

deoarece elementele a[1,i] = ∞ nu se vor lua in considerare.

La pasul p2 sunt necesare cel mult n-2 adunari si n-2

comparari. Se observa ca ordinul matricei A scade cu cate o

unitate la fiecare executie. In concluzie, vor fi necesare cel

mult un numar de ∑−

=

−−=2

1

)2)(1(2n

qnnq comparari si cel

mult un numar de ∑−

=

−−=

2

1 2)2)(1(n

q

nnq adunari .

Aplicand algoritmul lui Yen de n ori, vom determina

distantele minime de la x1 la toate celelalte varfuri, de la x2 la

celelalte varfuri, …..,de la xn la toate celelalte varfuri ale

grafului orientat, adica distantele minime intre oricare doua

varfuri ale grafului G.

Pentru aceasta sunt necesare cel mult n(n-1)(n-2)

comparari si n(n-1)(n-2) / 2 adunari, adica O(n3) .

Exemplul 5 Sa se determine distantele minime de la

varful x1 la celelalte varfuri ale grafului orientat G=(V,U), dat

in fig. 6.

21

A 1 2 3 4 5 6

1 0 1 4 ∞ ∞ ∞

2 ∞ 0 2 5 8 ∞

3 ∞ ∞ 0 2 5 8

4 ∞ ∞ ∞ 0 3 5

5 ∞ ∞ ∞ ∞ 0 1

6 ∞ ∞ ∞ ∞ ∞ 0

A-Matricea distantelor directe

In matricea distantelor directe A se observa ca pe

prima linie elementul minim este a[1,2] = 1, deci a*[1,2] =1

(io=2). Celelalte elemente ale primei linii se vor recalcula:

a[1,3]= min(a[1,3], a[1,2] + a[2,3] ) = 3;

a[1,4] = 6 ;a[1,5] = 9 ;a[1,6] = ∞ .

Se vor suprima linia si coloana de rang 2, obtinand

matricea in care se vor mentine vechile ranguri de linii si

coloane din A.

1 3 4 5 6

A(1) 1 2 3 4 5

1 1 0 3 6 9 ∞

3 2 ∞ 0 2 5 ∞

4 3 ∞ ∞ 0 3 5

5 4 ∞ ∞ ∞ 0 1

6 5 ∞ ∞ ∞ ∞ 0

22

Elementul minim, din prima linie, este a*[1,3] =

a[1,3] = 3 .

Continuand rationamentul, se vor obtine urmatoarele

matrice:

1 4 5 6

A(2) 1 2 3 4

1 1 0 5 8 ∞

4 2 ∞ 0 3 5

5 3 ∞ ∞ 0 1

6 4 ∞ ∞ ∞ 0

Se vede ca a*[1,4] = 5.

1 5 6

A(3) 1 2 3

1 1 0 8 10

5 2 ∞ 0 1

6 3 ∞ ∞ 0

Elementul obtinut este a*[1,5] = 8.

1 6

A(4) 1 2

1 1 0 9

6 2 ∞ 0

23

In final, se obtine a*[1,6] = 9.

Algoritmul se opreste in acest moment. Distantele

minime gasite sunt: a*[1,2] = 1; a*[1,3] = 3; a*[1,4] = 5;

a*[1,5] = 8 ; a*[1,6] = 9. Acestea sunt elementele minime

diferite de zero de pe prima linie din matricea curenta.

Pentru determinarea drumurilor de lungime minima de

la varful x1 la varful x6 se va proceda astfel:

Daca (xk , xj) este ultimul arc al unui drum minim de

la varful xi la varful xj, atunci a*[i,j] = a*[i,k] + a[k,j],

deoarece, daca consideram un drum minim de la xi la xk pe

care sa-l prelungim cu arcul (xk ,xj), lungimea acestui drum de

la xi la xj este egala cu a*[i,k] + a[k,j] = a*[i,j], adica este

drumul minim de la xi la xj al carui ultim arc este (xk,xj).

Prin urmare, daca consideram indicii k= k1,k2,…,ks

care satisfac relatia a*[i,j] = a*[i,k] + a[k,j], atunci arcele

),(),...,,(),,(21 jkjkjk xxxxxx

s sunt ultimele arce din

drumurile minime de la xi la xj.

Pentru fiecare din acesti indici se va repeta

procedeul, gasind ultimele arce care ajung in xk1 din drumurile

minime de la varful xi la varful xk1, luand in locul lui j pe k1

etc.

Daca nu exista nici un indice k≠i, j care sa verifice

egalitatea a*[i,j] = a*[i,k] + a[k,j], atunci rezulta ca arcul

(xi,xj) este singurul drum minim de la xi la xj. Continuand

24

rationamentul, se vor gasi toate drumurile minime de la xi la xj.

Pentru aplicatia considerata se vor regasi drumurile

minime: d1=(x1,x2,x3,x5,x6) si d2 =(x1,x2,x3,x4,x5,x6) .

Tematica propusa

1 Sa se arate ca un graf orientat G=(V,U) cat si

transpusul sau GT=(V,UT) cu UT={(x,y)/(y,x)∈U}, au aceleasi

componente tare conexe.

2 Sa se implementeze algoritmul matriceal pentru

identificarea componentelor tare conexe intr-un graf orientat.

3 Aratati ca un graf complet si tare conex este

hamiltonian.

4 Fie G=(V,U) un graf cu V={0,1,2,...,n-1} si A(nxn)

matricea sa de adiacenta. O astfel de matrice se poate

considera ca fiind matricea booleana a drumurilor de lungime

unu existente in G. Aratati ca numarul drumurilor netriviale de

lungime k de la varful i la varful j este dat de elementul

matriceal (Ak)i,j , iar existenta unor astfel de drumuri este data

de elementul matriceal (A(k))i,j (unde A(k) reprezinta puterea

booleana k a matricei A). De asemenea, daca (A(k))i,i=1

inseamna ca exista circuit de lungime k in graf, iar numarul

acestora este dat de elementul matriceal (Ak)i,i.

Determinati drumurile si circuitele ce exista in graful

25

orientat reprezentat prin matricea de adiacenta urmatoare:

0 0 0 1 1

1 0 0 0 1

1 1 0 0 0

1 1 1 0 0

0 0 1 0 1

5 Sa se implementeze in C algoritmii lui Roy-Floyd

si Yen.

6 Aplicati algoritmul lui Yen pe graful ponderat cu

urmatoarea matrice a costurilor:

A 1 2 3 4 5 6 7 8

1 0 2 10 6 ∞ ∞ ∞ ∞

2 ∞ 0 9 3 ∞ ∞ ∞ ∞

3 ∞ ∞ 0 ∞ 8 3 ∞ ∞

4 ∞ ∞ ∞ 0 2 ∞ 7 ∞

5 ∞ ∞ ∞ ∞ 0 6 5 6

6 ∞ ∞ ∞ ∞ ∞ 0 ∞ 7

7 ∞ ∞ ∞ ∞ ∞ ∞ 0 8

8 ∞ ∞ ∞ ∞ ∞ ∞ ∞ 0

26

Verificati-va cunostintele:

-1 Gradul exterior al unui varf x dintr-un graf orientat

este definit prin:

a) )(x+Γ

b) )(x−ω

c) )(x+Γ

d) )(x+ω .

-2 Cate grafuri orientate complete de ordin n 5≥ (n

numar natural ) exista?

a) 1 ; b) 2 ; c)

2n

; d)

23n

-3 Se considera urmatoarea matrice de adiacenta:

A 1 2 3 4 5 6 7 8

1 0 1 0 0 1 0 0 0

2 0 0 1 0 0 0 0 0

3 0 0 0 1 0 0 0 0

4 1 0 0 0 0 0 0 0

5 0 1 0 0 0 1 0 0

6 0 0 0 0 0 0 1 1

7 0 0 0 0 0 0 0 0

8 0 0 0 0 1 0 1 0

27

Graful orientat reprezentat prin acesata matrice este:

a) simetric

b) antisimetric

c) complet

d) tranzitiv