Teorie grafuri orientate C++

Un graf orientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor orientate, perechile de varfuri din multimea E sunt ordonate si se numesc arce. Ele au o directie spre care merg. Arcul format de varfurile x si y se noteaza cu (x,y), varful x se numeste extremitate initiala a arcului (x,y), iar varful y se numeste extremitate finala a arcului (x,y).

Daca exista un arc determinat de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu arcul pe care il formeaza. Fiecare extremitate a unui arc este considerata incidenta arcului respectiv.

1. Reprezentarea vizuala a grafurilor orientate:

1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
2. Fiecare arc se reprezinta vizual ca o sageata care pleaca din extremitatea initiala si ajunge in extremitatea finala.

Exemplu:

2. Gradul unui varf

In cazul grafurilor orientate exista 2 tipuri de grade pe care un varf le poate avea: gradul exterior si gradul interior.

Gradul exterior al varfului x se noteaza cu d⁺(x) si este egal cu numarul de arce care au ca extremitate initiala pe x. In alte cuvinte, gradul exterior al varfului x reprezinta numarul de arce care pleaca din acel varf.

Gradul interior al varfului x se noteaza d^– si este egal cu numarul de arce care au ca extremitate finala pe x. In alte cuvinte, gradul interior al unui varf x este egal cu numarul de arce care ajung in acel varf.

Spre exemplu, pentru graful de mai sus avem:

x	1	2	3	4	5	6
d+(x)	2	1	0	1	2	0
d–(x)	1	1	1	1	2	0

Teorema:

Suma gradelor interioare ale varfurilor unui graf orientat este egala cu suma gradelor exterioare ale varfurilor grafului si este egala cu numarul de arce din graf.

 Σd⁺(x) = Σd^–(x) = m

3. Notiunile de drum si circuit

Se numeste drum intr-un graf orientat o secventa de varfuri (x₁,x₂,…,x_p), astfel incat pentru oricare doua varfuri consecutive x_i si x_i+1 exista arcul (x_i,x_x+1). De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,1,3) este un drum de lungime 4.

Se numeste lungime a unui drum numarul de arce continute de acesta.

Un drum este elementar daca nu contine de mai multe ori acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,4) este un drum elementar de lungime 3.

Un drum este simplu daca nu contine de mai multe ori aceeasi muchie De exemplu, pentru graful de mai sus, secventa de varfuri (1,2) este un drum simplu de lungime 1.

Un circuit este un drum simplu pentru care extremitatea initiala coincide cu extremitatea finala. In alte cuvinte, drumul pleaca dintr-un varf si ajunge in acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (5,4,5,4,5) este un circuit, intrucat el pleaca din varful 1 si ajunge tot in varful 1.

Un circuit se numeste elementar daca nu contine de mai multe ori acelasi varf (exceptie facand extremitatile sale). De exemplu, pentru graful de mai sus, secventa de varfuri (1,2,5,1) este un circuit elementar.

Teoreme:

Un drum/circuit elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un drum/circuit elementar se numeste eulerian daca el trece prin fiecare arc al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’ = (V,E’) se numeste graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand arce din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea arcelor (1,2), (5,4) din graful initial de la inceputul postarii.

Un subgraf al lui G se obtine eliminand varfuri din graful G impreuna cu toate arcele incidente cu acestea.

Subgraful de mai sus a fost obtinut prin eliminare varfurilor 1,3 si 6 si a arcelor incidente cu acestea: (1,2), (1,3), (5,1) din graful initial.

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, toate arcele incidente cu varfurile eliminate, precum si alte arce din graf.

Teoreme:

Fie G un graf orientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2^m-1.

b) Numarul de subgrafuri ale lui G este 2ⁿ-1.

5. Tipuri speciale de grafuri orientate:

Un graf orientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful orientat complet cu n varfuri se numeste K_n si contine [n(n-1)]/2 muchii.

Exemplu:

Grafurile de mai sus sunt grafuri orientate complete cu 4 varfuri.

In cazul grafurilor orientate, pentru un numar fixat de varfuri pot exista mai multe grafuri complete.

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

• Category: Info