Teoria Grafurilor: Tipuri de Grafuri

---

1. Graf Parțial

1. Definiție:
   Un graf parțial al unui graf GGG este un graf care are:
   • Aceleași noduri ca GGG (VVV).
   • Un subset al muchiilor din GGG (E′⊆EE’ \subseteq EE′⊆E).
2. Exemplu:
   • Graful original GGG:

1–2–3

|   |

4–5

2. Graf parțial:

1–2   3

|     

4     

---

2. Subgraf

1. Definiție:
   Un subgraf al unui graf GGG este un graf care conține:
   • Un subset al nodurilor din GGG (V′⊆VV’ \subseteq VV′⊆V).
   • Toate muchiile dintre nodurile din V′V’V′ care apar și în GGG.
2. Exemplu:
   • Graful original GGG:

1–2–3

|   |

4–5

2. Subgraf:

1–2

    |

    5

---

3. Graf Plin (Graf Dens)

1. Definiție:
   Un graf este plin sau dens dacă numărul de muchii este apropiat de numărul maxim posibil ((n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}(2n​)=2n(n−1)​).
2. Proprietăți:
   • Un graf complet este întotdeauna un graf plin, dar un graf plin nu este neapărat complet.

---

4. Graf Complet

1. Definiție:
   Un graf complet este un graf în care există o muchie între fiecare pereche de noduri.
2. Proprietăți:
   • Numărul de muchii este: ∣E∣=n(n−1)2|E| = \frac{n(n-1)}{2}∣E∣=2n(n−1)​
3. Exemplu:
   Graful complet cu 4 noduri (K4K_4K4​):

1–2

|\ /|

| X |

|/ \|

3–4

---

5. Graf Turneu

1. Definiție:
   Un graf turneu este un graf orientat complet, în care pentru fiecare pereche de noduri există exact un arc care le conectează.
2. Proprietăți:
   • Fiecare pereche de noduri este conectată printr-un arc unic (unidirecțional).
3. Exemplu:

(1) → (2)

 ↑  ↘   ↓

(3) ← (4)

---

6. Graf Bipartit

1. Definiție:
   Un graf bipartit este un graf în care nodurile pot fi împărțite în două mulțimi disjuncte UUU și VVV, astfel încât toate muchiile conectează un nod din UUU cu un nod din VVV.
2. Proprietăți:
   • Nu conține cicluri de lungime impară.
   • Este utilizat în problemele de împerechere (matching).
3. Exemplu:

1–3

|   |

2–4

Mulțimile bipartite:

3. U={1,2}U = \{1, 2\}U={1,2}
4. V={3,4}V = \{3, 4\}V={3,4}

---

7. Graf Transpus

1. Definiție:
   Un graf transpus al unui graf orientat GGG este obținut prin inversarea direcției fiecărui arc din GGG.
2. Exemplu:
   • Graful GGG:

(1) → (2)

 ↑     ↓

(3) ← (4)

2. Graful transpus GTG^TGT:

(1) ← (2)

 ↓     ↑

(3) → (4)

---

8. Graf Ponderat

1. Definiție:
   Un graf ponderat este un graf în care fiecare muchie are o valoare asociată (greutate sau cost).
2. Proprietăți:
   • Greutățile pot fi utilizate pentru a calcula drumuri minime (ex.: algoritmul Dijkstra).
3. Exemplu:

1–2 (5)

|   |

(3) (2) | | 3–4 (4)

–

#### **9. Graf Tare Conex**

1. **Definiție:** 

Un **graf orientat** este **tare conex** dacă există un drum orientat între orice pereche de noduri (\( u \) și \( v \)).

2. **Proprietăți:**

– Este utilizat în analiza componentelor conexe ale grafurilor orientate.

3. **Exemplu:** 

(1) → (2) ↑ ↓ (3) ← (4)

Graful este tare conex deoarece există un drum orientat între orice două noduri.

–

#### **10. Comparație între tipuri de grafuri**

| Tip de Graf      | Proprietăți principale                                           | Aplicații                                       |

|––––––-|––––––––––––––––––––––|––––––––––––––––|

| **Graf Parțial**  | Subset de muchii ale unui graf                                   | Reducerea complexității unui graf              |

| **Subgraf**       | Subset de noduri și muchii ale unui graf                        | Analiza locală                                 |

| **Graf Complet**  | Fiecare pereche de noduri este conectată                       | Probleme de optimizare (ex.: comis-voiajor)    |

| **Graf Turneu**   | Orientat complet                                               | Modelarea turneelor                            |

| **Graf Bipartit** | Nodurile pot fi separate în două mulțimi disjuncte             | Probleme de împerechere                        |

| **Graf Transpus** | Direcția arcelor este inversată                                | Probleme de flux                               |

| **Graf Ponderat** | Fiecare muchie are o greutate                                  | Algoritmi de drumuri minime                    |

| **Graf Tare Conex** | Drumuri orientate între orice două noduri                    | Analiza conectivității grafurilor orientate    |

–

#### **11. Implementare exemplu: Graf complet**

„`

#include <iostream>

using namespace std;

void grafComplet(int n) {

 cout << „Matricea de adiacență pentru un graf complet:\n”;

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

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

         if (i == j)

             cout << „0 „;

         else

             cout << „1 „;

     }

     cout << endl;

 }

}

int main() {

 int n = 4;

 grafComplet(n);

 return 0;

}

---

12. Concluzie

• Grafurile sunt extrem de diverse și fiecare tip are aplicații practice specifice.
• Înțelegerea proprietăților fiecărui tip este crucială pentru utilizarea lor în probleme reale.
• Alegerea tipului de graf potrivit facilitează rezolvarea eficientă a problemelor.

Metode de Reprezentare a Grafurilor: Matricea de Adiacență

---

1. Ce este Matricea de Adiacență?

Matricea de adiacență este o metodă de reprezentare a unui graf (neorientat sau orientat) folosind o matrice binară AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde ∣V∣|V|∣V∣ este numărul de noduri din graf.

---

2. Definiție

Pentru un graf G=(V,E)G = (V, E)G=(V,E):

• A[i][j]=1A[i][j] = 1A[i][j]=1, dacă există o muchie (sau un arc, în cazul grafurilor orientate) între nodurile iii și jjj.
• A[i][j]=0A[i][j] = 0A[i][j]=0, altfel.

---

3. Caracteristici

1. Grafuri neorientate:
   • Matricea este simetrică (A[i][j]=A[j][i]A[i][j] = A[j][i]A[i][j]=A[j][i]).
   • Elementele de pe diagonala principală (A[i][i]A[i][i]A[i][i]) sunt 0 pentru grafuri fără bucle.
2. Grafuri orientate:
   • Matricea poate fi asimetrică (A[i][j]≠A[j][i]A[i][j] \neq A[j][i]A[i][j]=A[j][i]).
   • A[i][j]=1A[i][j] = 1A[i][j]=1 indică un arc orientat de la iii la jjj.
3. Grafuri ponderate:
   • În loc de valori binare (0 și 1), matricea conține greutățile muchiilor sau arcelor.

---

4. Avantaje și Dezavantaje

Avantaje	Dezavantaje
Acces rapid pentru verificarea existenței unei muchii (O(1)O(1)O(1)).	Necesită ( O(
Ușor de implementat și de utilizat.	Complexitatea spațială crește odată cu numărul de noduri.
Reprezentare simplă pentru grafuri dense.	Traversarea vecinilor unui nod necesită ( O(

---

5. Exemplu pentru Grafuri Neorientate

---

Graf:

1–2

|   |

4–3

Reprezentare:

• Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
• Muchii: E={(1,2),(1,4),(2,3),(3,4)}E = \{(1, 2), (1, 4), (2, 3), (3, 4)\}E={(1,2),(1,4),(2,3),(3,4)}

Matricea de adiacență:

  1  2  3  4

1 0  1  0  1

2 1  0  1  0

3 0  1  0  1

4 1  0  1  0

---

6. Exemplu pentru Grafuri Orientate

---

Graf:

(1) → (2)

 ↑      ↓

(4) ← (3)

Reprezentare:

• Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
• Arce: E={(1,2),(3,4),(4,1),(2,3)}E = \{(1, 2), (3, 4), (4, 1), (2, 3)\}E={(1,2),(3,4),(4,1),(2,3)}

Matricea de adiacență:

  1  2  3  4

1 0  1  0  0

2 0  0  1  0

3 0  0  0  1

4 1  0  0  0

---

7. Exemplu pentru Grafuri Ponderate

---

Graf:

1–2 (5)

|   |

(3) (2)

|   |

3–4 (4)

Reprezentare:

• Noduri: V={1,2,3,4}V = \{1, 2, 3, 4\}V={1,2,3,4}
• Muchii cu greutăți: E={(1,2,5),(1,3,3),(2,4,2),(3,4,4)}E = \{(1, 2, 5), (1, 3, 3), (2, 4, 2), (3, 4, 4)\}E={(1,2,5),(1,3,3),(2,4,2),(3,4,4)}

Matricea de adiacență:

  1  2  3  4

1 0  5  3  0

2 5  0  0  2

3 3  0  0  4

4 0  2  4  0

---

8. Implementare în C++

---

1. Matricea de adiacență pentru graf neorientat

#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 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ță pentru graful neorientat:\n”;

    afisareMatrice(n, matrice);

    return 0;

}

---

2. Matricea de adiacență pentru graf orientat

#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ță pentru graful orientat:\n”;

    afisareMatrice(n, matrice);

    return 0;

}

---

3. Matricea de adiacență pentru graf ponderat

#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 muchii ponderate

    matrice[0][1] = 5; // Muchie 1-2 cu greutatea 5

    matrice[0][2] = 3; // Muchie 1-3 cu greutatea 3

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

    matrice[2][3] = 4; // Muchie 3-4 cu greutatea 4

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

    afisareMatrice(n, matrice);

    return 0;

}

---

9. Concluzie

• Matricea de adiacență este o metodă simplă și eficientă pentru reprezentarea grafurilor dense.
• Este utilă pentru verificarea rapidă a existenței unei muchii.
• Pentru grafuri sparse, poate fi mai avantajos să se folosească lista de adiacență datorită economiei de memorie.