Teoria Grafurilor: Grafuri Neorientate – Noțiuni Introdutive 17
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.