Teorie grafuri orientate C++

Become a Patron!

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 (x1,x2,…,xp), astfel incat pentru oricare doua varfuri consecutive xi si xi+1 exista arcul (xi,xx+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.

graf orientat partial

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.

subgraf orientat

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 2m-1.

b) Numarul de subgrafuri ale lui G este 2n-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 Kn 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 🙂

5 Comments

  1. “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 acelasi varf. De exemplu, pentru graful de mai sus, secventa de varfuri (1,2) este un drum simplu de lungime 2.”

    Nu inteleg diferenta dintre graful elementar si cel simplu, ai putea sa o explici altfel?
    In plus, secventa de vf (1,2), nu ar trebui sa aiba lg=1? De ce lg=2?

    3

    Reply

    1. probabil a gresit omul cand le-a scris, daca teoria se aplica la fel ca la grafuri neorientate, atunci un grafic simplu daca nu contine acelasi arc de 2 ori si da lungimea drumului (1,2) e 1

      1

      Reply

    2. Salut. Legat de prima intrebare, un drum elementar nu contine de doua ori acelasi varf, in timp ce un drum simplu nu contine de doua ori aceeasi muchie. Iar drumul (1,2) are intr-adevar lungime 1. Ne cerem scuze pentru greseli si o zi buna.

      3

      Reply

Leave a Reply

Your email address will not be published. Required fields are marked *