Grafuri Orientate

Teorie

Un graf orientat este o pereche G = (X, U), unde:
• X este o mulțime finită de vârfuri.
• U este o mulțime de perechi ordonate de vârfuri, numite arce.

Exemple din viața reală:

• Drumuri cu sens unic între orașe
• Fluxuri de date într-o rețea
• Relații de dependență între task-uri

Proprietăți fundamentale:

• Vârfuri adiacente: x → y dacă există arcul (x,y)
• Grad intrare: număr de arce care intră în vârf
• Grad ieșire: număr de arce care ies din vârf
• Vârf izolat: grad intrare = 0 și grad ieșire = 0
• Lanț orientat: secvență de vârfuri consecutive legate de arce orientate
• Ciclu orientat: lanț a cărui extremitate finală coincide cu cea inițială
• Graf conex (putere de conexiune): există un drum între oricare două vârfuri (prin orientare)

Grafuri speciale:

• Graf complet orientat (tournament): există un arc între fiecare pereche de vârfuri, orientat într-un singur sens
• Graf aciclic orientat (DAG): graf fără cicluri orientate
• Lanț elementar: lanț cu toate vârfurile distincte
• Ciclu elementar: ciclu cu toate vârfurile distincte, cu excepția primului și ultimului

Metode de reprezentare

Matrice de adiacență

Matrice pătratică n×n: A[i][j] = 1 dacă există arcul (i→j), altfel 0.

Vârfuri: 1,2,3
Arce: (1→2),(2→3)
Matrice:
0 1 0
0 0 1
0 0 0
  

Listele vecinilor

Fiecare vârf are o listă cu vârfurile către care există arce:

1: 2
2: 3
3: -
  

Vectorul de arce

Se păstrează toate perechile de vârfuri care formează arce. În C++ putem folosi struct:

struct Arc {
    int v1;
    int v2;
};

Arc U[2];
U[0] = {1,2};
U[1] = {2,3};
  

Probleme C++ rezolvate

Problema 1

Exemplu:

#include <iostream>
using namespace std;

struct Arc {
    int v1;
    int v2;
};

int main() {
    int n = 3;
    Arc U[2] = {{1,2},{2,3}};
    for(int i=0;i<2;i++)
        cout << "(" << U[i].v1 << "→" << U[i].v2 << ") ";
    return 0;
}
  

Problema 2 (rezolvare teoretică)

Exemplu:

Se determină dacă un graf este DAG: verificăm dacă există cicluri orientate prin algoritmi DFS sau topologic.

Exerciții propuse

1. Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, are arcele (2,1), (3,2), (3,5), (4,2), (5,6), (6,4). Indicați numărul vârfurilor pentru care gradul interior este egal cu gradul exterior.
   a. 1   b. 2   c. 3   d. 4



2. Un graf orientat cu 6 vârfuri are arcele (1,4), (2,3), (2,5), (2,6), (3,1), (4,6), (5,4). Indicați numărul minim de arce ce trebuie adăugate pentru ca graful să aibă două componente tare conexe.
   a. 1   b. 2   c. 3   d. 4



3. Un graf orientat fără circuite are 12 vârfuri. Indicați numărul maxim de arce ale grafului.
   a. 12   b. 66   c. 72   d. 132



4. Un graf orientat are 6 vârfuri și arcele (1,2), (2,4), (2,6), (3,1), (4,3), (5,2), (5,6). Indicați un circuit elementar al acestuia.
   a. 1,2,4   b. 2,4,3,2   c. 3,1,2,3   d. 5,2,6,5



5. Indicați numărul maxim de vârfuri izolate pe care le poate avea un graf orientat cu 20 de vârfuri și 20 de arce.
   a. 4   b. 5   c. 14   d. 16



6. Oricare dintre cele 6 vârfuri ale unui graf orientat are proprietatea că suma gradelor intern și extern este 5. Indicați lungimea maximă a unui drum elementar în acest graf.
   a. 12   b. 8   c. 5   d. 4



7. Într-un oraș sunt 6 stații de metrou A, B, C, D, E și F, conectate prin pasaje unidirecționale: (A,B), (B,F), (C,D), (D,E), (E,C), (F,A), (F,D). Indicați numărul minim de pasaje cărora trebuie să li se schimbe sensul pentru ca graful să devină tare conex.
   a. 1   b. 2   c. 3   d. 5



8. O companie are 5 centre logistice: 1 și 4 livrează cafea, 2 și 5 ceai, iar 3 ciocolată. Benzile de transport sunt (1,4), (4,2), (5,2), (3,1). Indicați numărul minim de arce ce trebuie adăugate astfel încât graful să aibă trei componente tare conexe, fiecare corespunzând unui tip de produs.
   a. 1   b. 2   c. 3   d. 4



9. O zonă turistică are 21 de obiective numerotate de la 1 la 21. Din orice i se poate merge la 2*i (dacă ≤21), altfel la i-1. Indicați numărul maxim de vârfuri ale unui drum elementar pornind din 1.
   a. 6   b. 10   c. 15   d. 20



10. Un graf orientat cu 7 vârfuri are arcele (1,2), (2,3), (3,1), (3,5), (4,5), (5,6), (6,4), (7,6). Indicați numărul de vârfuri ale componentei tare conexe care conține vârful 3.
    a. 2   b. 3   c. 4   d. 5



11. Un depozit are 9 sectoare grupate în 3 zone cu număr par de sectoare. Fiecare culoar este unidirecțional și conectează sectoare din aceeași zonă. Indicați numărul maxim de culoare ce pot fi trasate astfel încât graful să aibă 3 componente tare conexe.
    a. 18   b. 24   c. 36   d. 72



12. Un graf orientat cu 5 vârfuri și arcele (1,3), (3,2), (2,1), (2,4), (4,5), (5,4). Indicați numărul de componente tare conexe.
    a. 1   b. 2   c. 3   d. 4



13. Un graf orientat are 9 arce și 3 componente tare conexe. Fiecare vârf are grad intern și extern nenule. Numărul minim de vârfuri este:
    a. 4   b. 5   c. 6   d. 7



14. Un graf orientat cu 6 vârfuri și arcele (1,3), (2,4), (2,5), (3,2), (4,6), (5,1), (6,3). Scrieți un drum elementar de lungime maximă.



15. Un graf orientat cu 6 vârfuri și 30 de arce este complet. Pentru a obține două componente tare conexe, una cu 4 vârfuri și alta cu 2 vârfuri, câte arce minim trebuie eliminate?
    a. 4   b. 6   c. 8   d. 10



16. Într-un graf orientat cel puțin două vârfuri au grad extern 2, un vârf are grad intern 4, iar un alt vârf are grad extern 3. Numărul minim de vârfuri este:
    a. 4   b. 5   c. 6   d. 7



17. Un graf orientat cu 7 vârfuri și arcele (1,5), (2,6), (3,7), (4,5), (5,7), (6,7), (7,2), (7,4). Indicați câte vârfuri au grad extern nul.
    a. 1   b. 2   c. 3   d. 4



18. Indicați matricea de adiacență a unui graf orientat cu 4 vârfuri căruia îi poate aparține drumul 1,2,4,2,3.
    a. 0 1 0 0
    1 0 0 1
    0 0 0 1
    0 1 0 0
    
    b. 0 1 0 0
    0 0 0 1
    0 1 0 0
    0 0 1 0
    
    c. 0 1 0 0
    0 0 1 1
    0 0 0 1
    0 1 0 0
    
    d. 0 0 1 0
    1 0 0 0
    0 1 0 1
    0 0 0 0



19. Scrieți matricea de adiacență a unui graf orientat cu 6 vârfuri și 7 arce, care conține exact două circuite elementare distincte.



20. Un graf orientat cu 8 vârfuri are arcul (i,j) dacă j divide i (i≠j) sau dacă i și j sunt ambele impare și i
    
    
21. Un graf orientat are 14 arce, 4 componente tare conexe, iar fiecare vârf are grad extern nenul. Numărul maxim de vârfuri este:
    a. 14   b. 12   c. 10   d. 8



22. Un graf orientat cu 6 vârfuri este reprezentat prin matricea:
    0 0 0 1 0 0
    0 0 0 0 1 1
    0 1 0 0 0 0
    0 0 0 0 1 0
    0 0 0 0 0 1
    0 0 0 0 0 0
    Scrieți un drum elementar de la vârful 2 la vârful 6.