Teoria Grafurilor

CAPITOLUL III

ELEMENTE DE TEORIA DIGRAFURILOR SI GRAFURILOR

Teoria digrafurilor si grafurilor este o ramura relativ tânara a matematicii. Prima lucrare de teoria grafurilor a fost scrisa de Euler cu doua secole în urma. În secolul trecut multe rezultate în teoria grafurilor au fost obtinute de Cayley si aplicate ulterior de Kirkhoff în studiul circuitelor electrice.

Studiul teoriei (di)grafurilor a fost puternic stimulat de aparitia în 1936, la Leipzig, a lucrarii lui D. König consacrata teoriei grafurilor orientate si neorientate.

Nu ne contrazicem daca afirmam ca teoria (di)grafurilor este o ramura foarte tânara a informaticii. Putem considera teoria (di)grafurilor, prin implicatiile sale, ca parte componenta a analizei si sintezei algoritmilor, a structurilor de date, a tehnicilor de programare, a proiectarii circuitelor electronice, a schemelor VLSI, a reprezentarii sistemelor si automatelor deterministe si stochastice.

Interesul pentru studiul teoriei (di)grafurilor a crescut foarte mult în ultimele decenii datorita multiplelor posibilitati de aplicare ale acesteia în elaborarea deciziilor optime în multe probleme economice, tehnice, în sociologie, în psihologie, în lingvistica matematica.

Teoria (di)grafurilor cu multiplele ei interferente cu algebra, geometria, calculul probabilitatilor este considerata ca facând parte din domeniul mai larg al combinatoricii.

1. Concepte fundamentale

Definitia 1. Se numeste digraf (graf directionat, graf orientat), cvartetul D = (V, A , a, b) unde:

- V este o multime nevida, denumita multimea vârfurilor;

- A este o multime oarecare, A ÍV´V, denumita multimea arcelor;

- a si b sunt aplicatii definite astfel:

a:A®V; a(a) reprezinta “vârful initial” pentru aÎA;

b:A®V; b(a) reprezinta “vârful final” pentru aÎA.

Observatie. Un digraf poate fi de asemenea definit ca fiind perechea D = (V, G ), unde:

- V este o multime nevida (multimea vârfurilor);

- G este o aplicatie multivoca a lui V în V.

Vârfurile vÎV se reprezinta prin puncte, iar arcele aÎA prin linii (arce) ce unesc vârfurile initial si final, orientate de la vârful initial spre cel final.

Exemplu.

Aceasta reprezentare geometrica corespunde digrafului D = (V, A , a, b) unde:

V = {v1, v2, v3, v4, v5};

A = {a1, a2, a3, a4, a5, a6, a7};

A 1 2 3 4 5 6 7

a(a) 3 1 2 4 3 5 1

b(a) 4 5 2 1 4 2 3

Definitia 2. Fie digraful D = (V, A , a, b) si a1, a2ÎA;

1) a1 si a2 se numesc paralele daca a(a1) = a(a2) si b(a1) = b(a2);

2) a1 se numeste bucla daca a(a1) = b(a1);

3) D se numeste fara paralelisme (prescurtat: d.f.p.) daca:

a(a1) = a(a2) si b(a1) = b(a2)Þ a1 º a2;

4) D se numeste simplu, daca este d.f.p. care nu poseda bucle.

Observatie. Într-un digraf fara paralelisme, fiecare arc este bine determinat de vârful initial si de vârful final:

aÎ A º (a(a), b(a))ÎV´ V. (1)

Definitia 3. Un digraf fara paralelisme este o pereche D = (V, A) unde:

- V este o multime nevida (multimea vârfurilor);

- A este o submultime a produsului cartezian V´ V (multimea arcelor).

Exemplu.

V = {v1, v2, v3, v4, v5};

A = {(v2,v3), (v4,v1), (v3,v3), (v5,v2)};

Observatie. Din definitia 3 se obtine definitia 1 folosind relatia (1).

Definitia 4. Fie D un d.f.p. si u, v, wÎ V;

1) D se numeste simetric daca: (v,w)Î AÞ (w,v)Î A;

2) D se numeste antisimetric daca: (v,w)Î A Þ (w,v)ÏA;

3) D se numeste tranzitiv daca: (u,v)Î A si (v,w)Î AÞ (u,w)Î A;

4) D se numeste complet daca: v¹ w, (v,w)Ï AÞ (w,v)Î A.