Teoria Grafurilor: Grafuri Orientate – Noțiuni Introdutive 22

---

1. Obiectivele lecției:

• Să înțeleagă conceptul de graf orientat și elementele sale fundamentale.
• Să învețe despre proprietățile și reprezentările grafurilor orientate.
• Să exploreze diferențele dintre grafurile orientate și cele neorientate.

---

2. Ce este un graf orientat?

Un graf orientat (sau digraf) este o structură matematică formată din:

• Noduri (vârfuri): Entitățile distincte ale grafului (VVV).
• Arce (muchii orientate): Legături direcționate între noduri (EEE).

Proprietăți:

1. Arcele sunt direcționate: Fiecare muchie (u,v)(u, v)(u,v) are un sens de la uuu la vvv.
2. Gradul unui nod:
   • Grad intrare (in-degree): Numărul de arce care intră în nodul vvv.
   • Grad ieșire (out-degree): Numărul de arce care ies din nodul vvv.
3. Drumuri orientate: Succesiuni de arce respectă direcția indicată.

---

3. Exemple de grafuri orientate

1. Graf simplu:

(1) → (2)

 ↑     ↓

(4) ← (3)

1. Arcele: {(1,2),(3,4),(4,1),(2,3)}\{(1, 2), (3, 4), (4, 1), (2, 3)\}{(1,2),(3,4),(4,1),(2,3)}
2. Grad intrare și ieșire:
   • degin(1)=1,degout(1)=1deg_{in}(1) = 1, deg_{out}(1) = 1degin​(1)=1,degout​(1)=1
   • degin(2)=1,degout(2)=1deg_{in}(2) = 1, deg_{out}(2) = 1degin​(2)=1,degout​(2)=1
   • degin(3)=1,degout(3)=1deg_{in}(3) = 1, deg_{out}(3) = 1degin​(3)=1,degout​(3)=1
   • degin(4)=1,degout(4)=1deg_{in}(4) = 1, deg_{out}(4) = 1degin​(4)=1,degout​(4)=1

---

4. Reprezentări ale grafurilor orientate

---

1. Matricea de adiacență

1. Definiție:
   O matrice AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde:
   • A[i][j]=1A[i][j] = 1A[i][j]=1 dacă există un arc de la nodul iii la nodul jjj.
   • A[i][j]=0A[i][j] = 0A[i][j]=0 altfel.
2. Exemplu:
   Graful:

(1) → (2)

 ↑     ↓

(4) ← (3)

Matricea de adiacență:

0 1 0 0

0 0 1 0

0 0 0 1

1 0 0 0

3. Implementare în C++:

#include <iostream>

using namespace std;

void afisareMatrice(int n, int matrice[100][100]) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cout << matrice[i][j] << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4; // Numărul de noduri

    int matrice[100][100] = {0};

    // Adăugare arce

    matrice[0][1] = 1; // Arc 1 → 2

    matrice[1][2] = 1; // Arc 2 → 3

    matrice[2][3] = 1; // Arc 3 → 4

    matrice[3][0] = 1; // Arc 4 → 1

    cout << „Matricea de adiacență:\n”;

    afisareMatrice(n, matrice);

    return 0;

}

---

2. Lista de adiacență

1. Definiție:
   Fiecare nod este asociat cu o listă de noduri către care există arce.
2. Exemplu:
   Graful:

(1) → (2)

 ↑     ↓

(4) ← (3)

Lista de adiacență:

1: 2

2: 3

3: 4

4: 1

3. Implementare în C++:

#include <iostream>

#include <vector>

using namespace std;

void afisareListaAdiacenta(int n, vector<int> lista[]) {

    for (int i = 0; i < n; i++) {

        cout << i + 1 << „: „;

        for (int vecin : lista[i]) {

            cout << vecin + 1 << ” „;

        }

        cout << endl;

    }

}

int main() {

    int n = 4; // Numărul de noduri

    vector<int> lista[100];

    // Adăugare arce

    lista[0].push_back(1); // Arc 1 → 2

    lista[1].push_back(2); // Arc 2 → 3

    lista[2].push_back(3); // Arc 3 → 4

    lista[3].push_back(0); // Arc 4 → 1

    cout << „Lista de adiacență:\n”;

    afisareListaAdiacenta(n, lista);

    return 0;

}

---

5. Tipuri de grafuri orientate

1. Graf orientat simplu:
   Nu conține arce multiple sau bucle.
2. Graf orientat ponderat:
   Fiecare arc are o greutate asociată.
3. Graf aciclic orientat (DAG):
   Nu conține cicluri directe.
4. Graf complet orientat:
   Există un arc între oricare două noduri (în ambele sensuri).

---

6. Aplicații ale grafurilor orientate

1. Rețele de flux:
   Modelarea transportului sau distribuției de resurse.
2. Planificarea activităților:
   Grafurile aciclice orientate (DAG) sunt utilizate pentru reprezentarea dependențelor între activități.
3. Drumuri minime:
   Algoritmi precum Dijkstra sau Bellman-Ford sunt utilizați pentru grafuri ponderate.

---

7. Activități practice pentru elevi

1. Implementați un program care determină gradul de intrare și gradul de ieșire pentru fiecare nod dintr-un graf orientat.
2. Scrieți o funcție care verifică dacă un graf orientat conține cicluri.
3. Extindeți implementările pentru a suporta grafuri ponderate.

---

8. Concluzie

• Grafurile orientate sunt structuri fundamentale pentru modelarea relațiilor direcționate.
• Ele au numeroase aplicații practice în matematică, informatică și științe.
• Înțelegerea reprezentării și caracteristicilor acestora este esențială pentru aplicarea lor în probleme complexe.