Teoria Grafurilor: Grafuri Neorientate – Tipuri de Grafuri 18
1. Obiectivele lecției:
- Să înțeleagă principalele tipuri de grafuri neorientate.
- Să învețe caracteristicile fiecărui tip de graf.
- Să exploreze exemple și aplicații practice pentru fiecare tip de graf.
2. Ce este un graf neorientat?
Un graf neorientat este format din:
- Noduri (sau vârfuri): Mulțimea VVV (nodurile).
- Muchii: Mulțimea EEE (perechi de noduri).
Într-un graf neorientat, muchiile nu au direcție, adică {u,v}={v,u}\{u, v\} = \{v, u\}{u,v}={v,u}.
3. Tipuri de grafuri neorientate
1. Graf complet
- Definiție:
Un graf complet este un graf în care există o muchie între oricare două noduri distincte. - Proprietăți:
- Numărul maxim de muchii într-un graf complet cu nnn noduri este: ∣E∣=(n2)=n(n−1)2|E| = \binom{n}{2} = \frac{n(n-1)}{2}∣E∣=(2n)=2n(n−1)
- Gradul fiecărui nod este n−1n-1n−1.
- Exemplu:
Un graf complet cu 4 noduri:
1–2
|\ /|
| X |
|/ \|
3–4
- Aplicații:
- Rețele complet conectate.
- Probleme de optimizare, cum ar fi problema comis-voiajorului.
2. Graf vid
- Definiție:
Un graf vid este un graf care nu conține muchii. - Proprietăți:
- Numărul de muchii este ∣E∣=0|E| = 0∣E∣=0.
- Fiecare nod are gradul 0.
- Exemplu:
Un graf vid cu 3 noduri:
1 2 3
- Aplicații:
- Reprezentarea entităților izolate.
3. Graf regulat
- Definiție:
Un graf este regulat dacă toate nodurile au același grad. - Proprietăți:
- Fiecare nod are ddd muchii incidente, unde ddd este constant pentru toate nodurile.
- Exemplu:
Un graf regulat de grad 2:
1–2
| |
4–3
- Aplicații:
- Rețele de distribuție cu conexiuni uniforme.
4. Graf bipartit
- Definiție:
Un graf este bipartit dacă mulțimea nodurilor poate fi împărțită în două submulțimi disjuncte UUU și VVV, astfel încât toate muchiile conectează un nod din UUU cu un nod din VVV. - Proprietăți:
- Nu conține cicluri de lungime impară.
- Exemplu:
Un graf bipartit cu U={1,2}U = \{1, 2\}U={1,2} și V={3,4,5}V = \{3, 4, 5\}V={3,4,5}:
1–3
| \ |
2 4–5
- Aplicații:
- Probleme de împerechere (matching) în rețele și grafuri.
5. Graf ciclic
- Definiție:
Un graf ciclic conține cel puțin un ciclu, adică un drum închis care trece printr-un set de noduri distincte. - Exemplu:
Un graf ciclic cu un ciclu 1→2→3→11 \to 2 \to 3 \to 11→2→3→1:
1–2
\ /
3
- Aplicații:
- Rețele care reprezintă drumuri circulare.
6. Graf aciclic
- Definiție:
Un graf care nu conține cicluri se numește aciclic. - Exemplu:
Un graf aciclic:
1–2–3
- Aplicații:
- Rețele de dependență (ex.: grafuri de precedență).
7. Graf conex și graf disconex
- Graf conex:
Un graf este conex dacă există un drum între oricare două noduri. - Graf disconex:
Un graf este disconex dacă există cel puțin un nod care nu este conectat la restul grafului. - Exemplu:
Graful conex:
1–2
\ / \
3–4
Graful disconex:
1 2–3
|
4
- Aplicații:
- Graful conex este folosit în probleme care necesită conectivitate completă (ex.: rețele de transport).
8. Graf ponderat
- Definiție:
Un graf ponderat asociază o valoare (cost sau greutate) fiecărei muchii. - Exemplu:
Un graf ponderat:
1–2 (5)
| |
(2) (3) | | 3–4 (1)
3. **Aplicații:**
– Probleme de optimizare, cum ar fi găsirea celui mai scurt drum (algoritmul lui Dijkstra).
–
#### **4. Reprezentarea tipurilor de grafuri**
1. **Graf complet:**
Matricea de adiacență este completă cu valori 1, cu excepția diagonalei principale (0).
2. **Graf bipartit:**
Mulțimea nodurilor poate fi împărțită în două liste disjuncte.
3. **Graf ponderat:**
Matricea de adiacență conține greutățile muchiilor în loc de valori binare.
–
#### **5. Exemple de implementare în C++**
–
##### **1. 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;
}
2. Graf bipartit
#include <iostream>
#include <vector>
using namespace std;
bool esteBipartit(vector<int> lista[], int n) {
vector<int> culori(n, -1);
culori[0] = 1;
vector<int> coada;
coada.push_back(0);
while (!coada.empty()) {
int nod = coada.front();
coada.erase(coada.begin());
for (int vecin : lista[nod]) {
if (culori[vecin] == -1) {
culori[vecin] = 1 – culori[nod];
coada.push_back(vecin);
} else if (culori[vecin] == culori[nod]) {
return false;
}
}
}
return true;
}
int main() {
int n = 4;
vector<int> lista[4] = {
{1, 3},
{0, 2},
{1, 3},
{0, 2}
};
if (esteBipartit(lista, n)) {
cout << „Graful este bipartit.\n”;
} else {
cout << „Graful nu este bipartit.\n”;
}
return 0;
}
6. Activități practice pentru elevi
- Realizați un program care verifică dacă un graf este complet.
- Scrieți o funcție care determină gradul fiecărui nod dintr-un graf regulat.
- Implementați o funcție care verifică dacă un graf este conex sau disconex.
7. Concluzie
- Grafurile neorientate pot fi clasificate în funcție de structura și proprietățile lor.
- Înțelegerea tipurilor de grafuri este esențială pentru aplicarea lor în diverse probleme informatice și matematice.
- Practica cu implementările ajută la stăpânirea conceptelor teoretice și la utilizarea lor în situații reale.