Grafuri

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 1 cu un nod din

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.