| Referate | Director web | Adauga link | Contact |



Graf orientat


Un graf orientat reprezinta o pereche ordonata de multimi G=(X,U), unde X este o multime finita si nevida, numita multimea nodurilor, si U este o multime formata din perechi ordonate de elemente ale lui X, numita multimea arcelor.


Exemplu

                 





In graful din fig. 1 multimea nodurilor este X={1, 2, 3, 4, 5, 6, 7} si multimea arcelor este U={u1, u2, u3, u4, u5, u6, u7, u8, u9, u10}={(1,2), (2,3), (3,4), (4,1), (3,5), (5,3), (5,6), (6,7), (7,6), (7,5)}.







2


Conexitate in grafuri orientate




Un graf G este conex, daca oricare ar fi doua varfuri ale sale, exista un lant care le leaga.

Un lant intr-un graf orientat este un sir de arce {u1, u 2, u3 , …, un} cu proprietatea ca oricare doua arce consecutive au o extremitate comuna. Altfel spus, un lant este un traseu care uneste prin arce doua noduri numite extremitatile lantului, fara a tine cont de orientarea arcelor componente.


Exemplu




                                 


Graful este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lant. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lantul {u5, u3}, dar si pe traseul de noduri (4,1,2) stabilind lantul {u6, u2}



3


 



Acest graf nu este conex.

Luand submultimea de noduri {1,2,3}, putem spune ca intre oricare doua noduri din aceasta submultime exista cel putin un lant., de exemplu lantul {u1, u2} sau {u3, u1}. La fel stau lucrurile cu submultimea de noduri {4,5,6}. Dar nu ptuem gasi un lant intre un nod din prima submultime si un nod din a doua submultime.

Plecand dintr-un nod al primei submultimi si deplasandu-ne pe arce, nu avem cum sa trecem in a doua submultime pentru ca nu exista nici un arc direct care sa lege cele doua submultimi. De exemplu plecand din nodul 1 putem ajunge in nodul 2 pe traseul {u3, u2}, dar de aici nu putem ajunge mai departe in nodul 4, deci nu exista lant de la 2 la 4.





4


Componenta conexa


Componenta conexa a unui graf G=(X, U), reprezinta un subgraf G1=(X1, U1) conex, a lui G, cu proprietatea ca nu exista nici un lant care sa lege un nod din X cu un nod din X-X 1 (pentru orice nod, nu exista un lant intre acel nod si nodurile care nu fac parte din subgraf).


De exemplu graful din fig. 3 nu este conex , insa in el distingem doua componente conexe: G1 =(X1, U1), unde X1={1,2,3} si U1={u1, u2, u3}; si G2=(X2, U2), unde X2={4,5,6} si U2={u4, u5}.  


Graf tare conex


Graful tare conex este un graf orientat G=(X, U), daca pentru oricare doua noduri x si y apartin lui X, exista un drum de la x la y precum si un drum de la y la x.


Exemplu


5




Graful cu n=3 din fig. 4 este tare conex.

Pentru a demonstra acest lucru, formam toate perechile posibile de noduri distincte (x, y) cu x, y apartin multimii {1,2,3}, si pentru fiecare astfel de pereche cautam un drum de la x la y si un drum de la y la x.


  • x=1, y=2

De la 1 la 2 drumul [1,3,2], pe arcele (1,3) si (3,2);

De la 2 la 1 drumul [2,3,1], pe arcele (2,3) si (3,1).

  • x=1, y=3

De la 1 la 3 drumul [1,2,3], pe arcele (1,2) si (2,3);

De la 3 la 1 drumul [3,2,1], pe arcele (3,2) si (2,1).

  • x=2, y=3

De la 2 la 3 drumul [2,1,3], pe arcele (2,1) si (1,3);

De la 3 la 2 drumul [3,1,2], pe arcele (3,1) si (1,2).






Componenta tare conexa


Un subgraf se obtine dintr-un graf G= (X, U) eliminand niste varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase.

Fie un subgraf tare conex G1=(X1, U1) al grafului G=(X, U). Adaugam la subgraf un nod x care nu face parte din multimea nodurilor sale (x apartine X-X1). Obtinem astfel multimea de varfuri X1 reunit cu {x}. Subgraful indus pe multimea X1 reunit cu {x} se obtine luand si arcele care trec prin nodul x.


Daca acest subgrafnu mai este tare conex, atunci el se numeste componenta tare conexa.



Exemplu


6

Acesta este graful G=(X,U) tare conex.

Din el eliminam nodul 4.


Am obtinut astfel subgraful tare conex G1=(X1, U1).

Acestui graf ii adaugam un nod x care nu  face parte din multimea nodurilor subgrafului G1.




7





Graful obtinut  este componenta tare conexa.







Problema


Stabiliti daca graful de mai jos este sau nu conex.





8

X= {1, 2, 3, 4, 5};

U= {u1, u2, u3, u4, u5, u6, u7, u8, u9, u10, u11, u12, u13, u14, u15, u16}={(1,2), (2,1), (3,2), (2,3), (4,3), (3,4), (1,4), (4,1), (2,5), (5,2), (3,5), (5,3), (4,5), (5,4), (1,5), (5,1)}.


De la 1 la 2 pe drumul [1,5,2] sau [1,5,4,3,2], etc.

De la 1 la 3 pe drumul [1,5,3] sau [1,5,2,3], etc.

De la 1 la 4 pe drumul [1,5,4] sau [1,5,2,3,4], etc.

De la 1 la 5 pe drumul [1,2,5] sau [1,4,5], etc.


De la 2 la 3 pe drumul [2,5,3] sau [2,1,5,3],etc.

De la 2 la 4 pe drumul [2,5,4] sau [2,3,5,4], etc.

De la 2 la 5 pe drumul [2,1,5] sau [2,3,5], etc.


De la 3 la 4 pe drumul [ 3,5,4] sau [3,2,5,4], etc.

De la 3 la 5 pe drumul [3,2,5] sau [3,4,5], etc.

De la 4 la 5 pe drumul [4,1,5] sau [4,3,5], etc.


9

Bibliografie:


Adam Romica,          - Structuri de date , Ed.  

  Ivan Ion                     Petrion, Bucuresti, 1992.

          

Ivasc Cornelia,            - Bazele informaticii , Ed.

Pruna Mona                 Petrion, Bucuresti, 1995.

- Tehnici de programare.

  Aplicatii, Ed. Petrion

  Bucuresti, 1999.

Stoilescu Dorian          - Culegere de C/C++,

                                       Ed. Radial, Bucuresti, 1998.


                    



10