Teoria Grafurilor: Grafuri Orientate – Noțiuni Introdutive

---

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.

Teoria Grafurilor: Adiacență, Incidență, Grad, Drum și Circuit

---

1. Adiacență

1. Definiție:
   Două noduri sunt adiacente dacă există o muchie (în grafuri neorientate) sau un arc (în grafuri orientate) între ele.
2. Exemple:
   • Într-un graf neorientat, uuu și vvv sunt adiacente dacă {u,v}∈E\{u, v\} \in E{u,v}∈E.
   • Într-un graf orientat, uuu este adiacent cu vvv dacă există un arc (u,v)∈E(u, v) \in E(u,v)∈E.
3. Reprezentări:
   • Matricea de adiacență: A[i][j]=1A[i][j] = 1A[i][j]=1 dacă iii și jjj sunt adiacente, altfel 000.
   • Lista de adiacență: Fiecare nod are o listă de noduri adiacente.
4. Exemplu grafic:

1–2

|   |

4–3

4. Nodul 1 este adiacent cu nodurile 2, 3, 4.
5. Nodul 2 este adiacent cu nodurile 1, 3.

---

2. Incidență

1. Definiție:
   • O muchie (în grafuri neorientate) sau un arc (în grafuri orientate) este incidentă la un nod dacă acel nod este unul dintre extremitățile muchiei sau arcului.
2. Exemplu:
   • Pentru muchia {1,2}\{1, 2\}{1,2}, nodurile 1 și 2 sunt incidente.
   • Într-un graf orientat, pentru arcul (1,2)(1, 2)(1,2), nodul 1 este incident la origine, iar nodul 2 este incident la destinație.
3. Reprezentare prin matricea de incidență:
   • O matrice I[i][j]I[i][j]I[i][j], unde:
     • I[i][j]=1I[i][j] = 1I[i][j]=1, dacă nodul iii este incident la muchia jjj.
     • I[i][j]=−1I[i][j] = -1I[i][j]=−1, dacă iii este nodul de origine (în grafuri orientate).
4. Exemplu grafic:

1–2

|   |

4–3

4. Muchia {1,2}\{1, 2\}{1,2} este incidentă la nodurile 1 și 2.

---

3. Grad

1. Definiție:
   Gradul unui nod reprezintă numărul de muchii incidente la acel nod.
2. Tipuri de grad:
   • Graf neorientat: Gradul unui nod este numărul de muchii incidente.
   • Graf orientat:
     • Grad intrare (degindeg_{in}degin​): Numărul de arce care intră în nod.
     • Grad ieșire (degoutdeg_{out}degout​): Numărul de arce care ies din nod.
3. Proprietăți:
   • Într-un graf neorientat, suma gradelor tuturor nodurilor este de două ori numărul muchiilor: ∑v∈Vdeg(v)=2∣E∣\sum_{v \in V} deg(v) = 2|E|v∈V∑​deg(v)=2∣E∣
4. Exemplu grafic:

1–2

|   |

4–3

4. Gradul nodului 1: deg(1)=3deg(1) = 3deg(1)=3.
5. Gradul nodului 2: deg(2)=2deg(2) = 2deg(2)=2.

---

4. Drum

1. Definiție:
   Un drum este o secvență de noduri conectate prin muchii sau arce, unde fiecare muchie/arce este parcursă o singură dată.
2. Tipuri de drumuri:
   • Drum simplu: Toate nodurile sunt distincte.
   • Drum elementar: Toate muchiile sunt distincte.
   • Drum circuit: Pornim și revenim la același nod, dar nodurile intermediare sunt distincte.
3. Exemplu grafic:

1–2

|   |

4–3

3. Drum simplu: 1→2→31 \to 2 \to 31→2→3.
4. Drum circuit: 1→2→3→4→11 \to 2 \to 3 \to 4 \to 11→2→3→4→1.

---

5. Circuit

1. Definiție:
   Un circuit este un drum care începe și se termină în același nod, iar toate nodurile intermediare sunt distincte.
2. Proprietăți:
   • Circuitul conține cel puțin trei noduri.
   • În grafuri orientate, sensul fiecărui arc trebuie respectat.
3. Exemplu grafic:

1–2

|   |

4–3

3. Circuit: 1→2→3→4→11 \to 2 \to 3 \to 4 \to 11→2→3→4→1.

---

6. Implementări în C++

---

1. Matricea de adiacență și gradul fiecărui nod

#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;

    }

}

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

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

        int grad = 0;

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

            if (matrice[i][j] == 1) grad++;

        }

        cout << „Gradul nodului ” << i + 1 << „: ” << grad << endl;

    }

}

int main() {

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

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

    // Adăugare muchii

    matrice[0][1] = matrice[1][0] = 1; // Muchie 1-2

    matrice[0][3] = matrice[3][0] = 1; // Muchie 1-4

    matrice[1][2] = matrice[2][1] = 1; // Muchie 2-3

    matrice[3][2] = matrice[2][3] = 1; // Muchie 4-3

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

    afisareMatrice(n, matrice);

    cout << „\nGradurile nodurilor:\n”;

    calculeazaGrad(n, matrice);

    return 0;

}

---

2. Detectarea unui drum simplu folosind DFS

#include <iostream>

#include <vector>

using namespace std;

void dfs(int nod, vector<int> lista[], vector<bool>& vizitat) {

    cout << nod + 1 << ” „;

    vizitat[nod] = true;

    for (int vecin : lista[nod]) {

        if (!vizitat[vecin]) {

            dfs(vecin, lista, vizitat);

        }

    }

}

int main() {

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

    vector<int> lista[4]; // Lista de adiacență

    // Adăugare muchii

    lista[0].push_back(1); lista[1].push_back(0); // Muchie 1-2

    lista[0].push_back(3); lista[3].push_back(0); // Muchie 1-4

    lista[1].push_back(2); lista[2].push_back(1); // Muchie 2-3

    lista[3].push_back(2); lista[2].push_back(3); // Muchie 4-3

    vector<bool> vizitat(n, false);

    cout << „Drum simplu pornind de la nodul 1: „;

    dfs(0, lista, vizitat);

    cout << endl;

    return 0;

}

---

7. Concluzie

• Adiacența și incidența sunt relațiile fundamentale dintre noduri și muchii.
• Gradul unui nod indică numărul de conexiuni directe ale acestuia.
• Drumurile și circuitele sunt concepte cheie pentru analiza conectivității în grafuri.
• Înțelegerea acestor noțiuni este esențială pentru aplicațiile mai avansate ale teoriei grafurilor.