Teoria Grafurilor: Grafuri Neorientate – Noțiuni Introductive
1. Obiectivele lecției:
- Să înțeleagă conceptul de graf și elementele sale fundamentale.
- Să învețe definiția și proprietățile unui graf neorientat.
- Să exploreze noțiuni introductive precum muchii, noduri, grade, conectivitate și reprezentări.
2. Ce este un graf?
- Definiție generală:
Un graf este o structură matematică care reprezintă relațiile dintre entități. Este format din:- Noduri (sau vârfuri): Elementele individuale, notate de obicei cu litere sau numere (VVV).
- Muchii: Legături între perechi de noduri (EEE).
- Graf neorientat:
Într-un graf neorientat, muchiile nu au direcție. Dacă uuu și vvv sunt două noduri, o muchie între ele este notată {u,v}\{u, v\}{u,v}, iar relația este simetrică: {u,v}={v,u}\{u, v\} = \{v, u\}{u,v}={v,u}.
3. Elemente fundamentale ale unui graf neorientat
- Noduri (Vârfuri):
Mulțimea tuturor nodurilor unui graf se notează cu VVV și ∣V∣|V|∣V∣ reprezintă numărul nodurilor. - Muchii:
Mulțimea tuturor muchiilor unui graf se notează cu EEE și ∣E∣|E|∣E∣ reprezintă numărul muchiilor. - Gradul unui nod:
Gradul unui nod uuu este numărul de muchii care ies din uuu. Se notează cu deg(u)deg(u)deg(u). - Conectivitate:
- Un graf este conex dacă există un drum între orice două noduri.
- Un graf este disconex dacă există cel puțin un nod izolat sau o componentă separată.
- Ciclu:
Un ciclu este o secvență de noduri distincte v1,v2,…,vkv_1, v_2, \dots, v_kv1,v2,…,vk unde vkv_kvk se conectează din nou la v1v_1v1. - Buclă:
O muchie care conectează un nod la el însuși.
4. Exemple simple de grafuri neorientate
- Graf complet:
Într-un graf complet cu nnn noduri, fiecare pereche de noduri este conectată. Numărul total de muchii este (n2)=n(n−1)2\binom{n}{2} = \frac{n(n-1)}{2}(2n)=2n(n−1). - Graf vid:
Un graf fără muchii. - Graf regulat:
Toate nodurile au același grad.
5. Reprezentarea grafurilor neorientate
- Matricea de adiacență:
O matrice binară AAA de dimensiune ∣V∣×∣V∣|V| \times |V|∣V∣×∣V∣, unde:- A[i][j]=1A[i][j] = 1A[i][j]=1 dacă există o muchie între nodurile iii și jjj.
- A[i][j]=0A[i][j] = 0A[i][j]=0 altfel.
Exemplu pentru un graf cu 4 noduri:
1–2
| |
4–3
Matricea de adiacență:
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
- Lista de adiacență:
Fiecare nod este asociat cu o listă de vecini.
Exemplu pentru același graf:
1: 2, 3, 4
2: 1, 3
3: 1, 2, 4
4: 1, 3
- Lista muchiilor:
Fiecare muchie este reprezentată ca o pereche de noduri.
Exemplu:
(1, 2), (1, 3), (1, 4), (2, 3), (3, 4)
6. Aplicații ale grafurilor neorientate
- Rețele de transport:
Reprezentarea rutelor între locații. - Rețele de comunicații:
Modelează conexiuni între dispozitive sau servere. - Rețele sociale:
Reprezintă relațiile dintre persoane. - Probleme de optimizare:
Probleme precum găsirea celui mai scurt drum sau a unei rute optime.
7. Proprietăți fundamentale ale grafurilor neorientate
- Sumă a gradelor nodurilor:
Suma gradelor tuturor nodurilor dintr-un graf 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∣
- Numărul maxim de muchii:
Pentru un graf cu nnn noduri, numărul maxim de muchii este:
n(n−1)2\frac{n(n-1)}{2}2n(n−1)
- Grafuri bipartite:
Un graf este bipartit dacă nodurile pot fi împărțite în două mulțimi disjuncte UUU și VVV, astfel încât toate muchiile să conecteze un nod din UUU cu un nod din VVV.
8. Exemple practice pentru implementare
1. Reprezentarea grafului cu matrice de adiacență
#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ăr de noduri
int matrice[100][100] = {0};
// Adăugare muchii
matrice[0][1] = matrice[1][0] = 1; // Muchie între 1 și 2
matrice[0][2] = matrice[2][0] = 1; // Muchie între 1 și 3
matrice[0][3] = matrice[3][0] = 1; // Muchie între 1 și 4
matrice[1][2] = matrice[2][1] = 1; // Muchie între 2 și 3
matrice[2][3] = matrice[3][2] = 1; // Muchie între 3 și 4
// Afișare matrice
afisareMatrice(n, matrice);
return 0;
}
2. Reprezentarea grafului cu lista de adiacență
#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ăr de noduri
vector<int> lista[100];
// Adăugare muchii
lista[0].push_back(1); lista[1].push_back(0);
lista[0].push_back(2); lista[2].push_back(0);
lista[0].push_back(3); lista[3].push_back(0);
lista[1].push_back(2); lista[2].push_back(1);
lista[2].push_back(3); lista[3].push_back(2);
// Afișare lista de adiacență
afisareListaAdiacenta(n, lista);
return 0;
}
9. Activități practice pentru elevi
- Realizați o funcție care verifică dacă un graf este complet.
- Scrieți un program care determină gradul fiecărui nod dintr-un graf.
- Implementați o funcție care verifică dacă un graf este bipartit.
10. Concluzie
- Grafurile neorientate sunt structuri fundamentale în teoria grafurilor, fiind utile pentru modelarea relațiilor simetrice.
- Reprezentările matriceale și lista de adiacență sunt cele mai comune metode de implementare.
- Înțelegerea noțiunilor introductive este esențială pentru aplicarea grafurilor în probleme mai complexe.
Teoria Grafurilor: Grafuri Neorientate – Tipuri de Grafuri
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.