|

Teoria Grafurilor: Tipuri de Grafuri 24


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

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

  1. 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:

  1. U={1,2}U = \{1, 2\}U={1,2}
  2. 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)

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

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *