🕸️
Ce este un graf?
🌐 Analogie: Grafuri = Rețele
Imaginează-ți o rețea de drumuri între orașe:
- Fiecare oraș este un nod (sau vârf)
- Fiecare drum dintre două orașe este o muchie (sau arc)
- Dacă drumul e cu sens unic → graf orientat
- Dacă poți circula în ambele sensuri → graf neorientat
Definiție formală: Un graf G = (V, E) este o pereche formată din:
- V = mulțimea vârfurilor (nodurilor), |V| = n
- E = mulțimea muchiilor (arcelor), |E| = m
G = ({1,2,3,4,5}, {(1,2),(1,4),(2,3),(2,5),(4,5),(3,5)}) — n=5, m=6
Adiacență
Două noduri sunt adiacente dacă există o muchie între ele. Muchia este incidentă cu ambele noduri.
Gradul unui nod
Numărul de muchii incidente. La graf orientat: grad interior (d⁻) + grad exterior (d⁺).
📐
Tipuri de grafuri
Graf neorientat
Muchiile nu au sens: {u,v} = {v,u}
Graf orientat (digraf)
Arcele au sens: (u,v) ≠ (v,u)
Graf ponderat
Fiecare muchie are un cost/greutate w(u,v)
Graf complet Kn
Un graf în care orice două noduri sunt adiacente (există muchie între oricare pereche).
K₃ — 3 muchii
K₄ — 6 muchii
K₅ — 10 muchii
Subgraf și graf parțial
Subgraf
Se obține din G prin eliminarea unor noduri (și a tuturor muchiilor incidente cu ele). G' = (V', E') cu V' ⊆ V.
Graf parțial
Se obține din G prin eliminarea unor muchii (nodurile rămân toate). G' = (V, E') cu E' ⊆ E.
Graf original G
Subgraf (fără nodul 4)
Graf parțial (fără muchia 1-4)
Alte tipuri importante
| Tip | Definiție | Proprietate |
|---|---|---|
| Graf nul | Fără muchii (E = ∅) | m = 0 |
| Graf regulat | Toate nodurile au același grad k | Grad constant k |
| Graf bipartit | V se partiționează în V₁ ∪ V₂, muchii doar între V₁ și V₂ | Colorabil cu 2 culori |
| Arbore | Graf conex aciclic | m = n − 1 |
| Graf hamiltonian | Conține un ciclu care trece prin fiecare nod exact o dată | NP-complet de verificat |
| Graf eulerian | Conține un ciclu care trece prin fiecare muchie exact o dată | Toate gradele sunt pare |
📐
Formule esențiale — Teoria Grafurilor
Notații: n = |V| (număr noduri), m = |E| (număr muchii), d(v) = gradul nodului v, d⁺(v) = grad exterior, d⁻(v) = grad interior.
📊 Formule pentru grafuri neorientate
| Formula | Descriere | Când se folosește |
|---|---|---|
| ∑ d(v) = 2m | Suma gradelor = 2 × nr. muchii | Orice graf neorientat (lema strângerii de mână) |
| 0 ≤ m ≤ n(n−1)/2 | Nr. maxim de muchii | Graf simplu (fără bucle/multimuchii) |
| m = n(n−1)/2 | Nr. muchii graf complet Kn | Identificare graf complet |
| 0 ≤ d(v) ≤ n−1 | Grad minim/maxim posibil | Validare secvență grafică |
| m ≥ n − 1 | Condiție necesară conexitate | Graf conex |
| m = n − 1 (conex) | Arbore (graf conex aciclic) | Verificare arbore |
| nr. componente = n − m | Pentru păduri (grafuri fără cicluri) | Numărare componente în păduri |
| Nr. noduri izolate = n − ∑[d(v)>0] | Noduri cu grad 0 | Identificare noduri izolate |
📊 Formule pentru grafuri orientate
| Formula | Descriere |
|---|---|
| ∑ d⁺(v) = ∑ d⁻(v) = m | Suma gradelor interioare = suma gradelor exterioare = nr. arce |
| 0 ≤ m ≤ n(n−1) | Nr. maxim de arce (graf orientat simplu) |
| 0 ≤ d⁺(v) ≤ n−1 | Grad exterior maxim |
| 0 ≤ d⁻(v) ≤ n−1 | Grad interior maxim |
📊 Formule graf complet Kn
| n | Kn muchii | Formula |
|---|---|---|
| 3 | 3 | m = n(n−1)/2 Fiecare nod are gradul n−1 Graf regulat de grad n−1 |
| 4 | 6 | |
| 5 | 10 | |
| 6 | 15 | |
| 10 | 45 |
📊 Lanțuri, cicluri, conexitate
| Concept | Definiție |
|---|---|
| Lanț | Secvență de noduri v₁, v₂, ..., vk astfel încât {vi, vi+1} ∈ E |
| Lanț elementar | Lanț în care nodurile nu se repetă |
| Ciclu | Lanț în care v₁ = vk (începe și se termină în același nod) |
| Ciclu elementar | Ciclu unde nodurile (cu excepția primului=ultimul) nu se repetă |
| Graf conex | Între oricare două noduri există cel puțin un lanț |
| Componentă conexă | Subgraf maximal conex (nu mai poate fi extins) |
| Graf tare conex | Graf orientat: între oricare două noduri u,v există drum de la u la v ȘI de la v la u |
Rezumat formule BAC (cele mai cerute):
- ∑ d(v) = 2m (lema strângerii de mână)
- Kn are n(n−1)/2 muchii
- Arbore conex: m = n − 1
- Graf eulerian ⟺ conex + toate gradele pare
- Graf bipartit ⟺ nu conține cicluri de lungime impară
💾
Reprezentarea grafurilor în C++
1. Matrice de adiacență
a[i][j] = 1 dacă există muchia (i,j), 0 altfel. Spațiu: O(n²).
int a[101][101], n, m; // Citire graf neorientat fin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; fin >> x >> y; a[x][y] = a[y][x] = 1; // neorientat: simetric } // Grad nod v: int grad = 0; for (int j = 1; j <= n; j++) grad += a[v][j]; // O(n)
2. Liste de adiacență
Pentru fiecare nod, o listă cu vecinii săi. Spațiu: O(n + m).
int n, m; vector<int> adj[101]; // liste de adiacență fin >> n >> m; for (int i = 1; i <= m; i++) { int x, y; fin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); // neorientat } // Gradul nodului v = adj[v].size() // Vecinii: for (int vec : adj[v]) ...
3. Lista de muchii
struct Muchie { int x, y, cost; }; Muchie edges[10001]; for (int i = 1; i <= m; i++) fin >> edges[i].x >> edges[i].y >> edges[i].cost;
Când folosim ce?
- Matrice: n ≤ 100, accces rapid a[i][j] în O(1), grad ușor de calculat
- Liste: n mare (10⁴–10⁵), parcurgeri BFS/DFS eficiente O(n+m)
- Lista de muchii: algoritmi pe muchii (Kruskal), sortare după cost
🚶
Parcurgeri: BFS și DFS
BFS (Breadth-First Search)
Parcurgere în lățime — folosește coadă. Vizitează nodurile nivel cu nivel (cele mai apropiate primele).
Complexitate: O(n + m)
DFS (Depth-First Search)
Parcurgere în adâncime — folosește stivă (sau recursie). Merge cât de adânc posibil înainte de a reveni.
Complexitate: O(n + m)
BFS — Parcurgere în lățime
#include <queue> bool vizitat[101]; int dist[101]; // distanța de la start void BFS(int start) { queue<int> Q; Q.push(start); vizitat[start] = true; dist[start] = 0; while (!Q.empty()) { int nod = Q.front(); Q.pop(); for (int vec : adj[nod]) { if (!vizitat[vec]) { vizitat[vec] = true; dist[vec] = dist[nod] + 1; Q.push(vec); } } } } // BFS găsește drumul minim (ca nr. muchii) de la start la orice nod
DFS — Parcurgere în adâncime
bool vizitat[101]; void DFS(int nod) { vizitat[nod] = true; // Prelucrare nod curent for (int vec : adj[nod]) { if (!vizitat[vec]) { DFS(vec); // merge mai adânc } } } // Numărare componente conexe: int nrComp = 0; for (int i = 1; i <= n; i++) { if (!vizitat[i]) { DFS(i); nrComp++; // fiecare DFS nou = componentă nouă } }
Aplicații clasice:
- BFS: distanța minimă, verificare bipartit, nivele
- DFS: componente conexe, ciclu, sortare topologică
- Ambele: verificare conexitate, verificare drum între 2 noduri
⭐
Grafuri speciale — Formule și proprietăți
🌳 Arbori
Echivalențe (pentru graf conex G cu n noduri):
- G este arbore ⟺ G are n−1 muchii
- G este arbore ⟺ G este conex și aciclic
- G este arbore ⟺ între oricare 2 noduri există exact un lanț
- G este arbore ⟺ eliminarea oricărei muchii îl deconectează
🔄 Graf Eulerian
| Proprietate | Condiție |
|---|---|
| Ciclu eulerian (revine la start) | Graf conex + toate gradele sunt pare |
| Lanț eulerian (start ≠ end) | Graf conex + exact 2 noduri de grad impar (sunt capetele) |
🔁 Graf Hamiltonian
Condiție suficientă (Teorema lui Dirac): Dacă n ≥ 3 și d(v) ≥ n/2 pentru orice nod v, atunci graful este hamiltonian.
Observație: Nu există condiție necesară și suficientă simplă! Verificarea este NP-completă.
Observație: Nu există condiție necesară și suficientă simplă! Verificarea este NP-completă.
📊 Secvență grafică
O secvență d₁ ≥ d₂ ≥ ... ≥ dn este secvență grafică (realizabilă ca graf simplu) dacă și numai dacă:
Teorema Erdős–Gallai: ∑di este pară ȘI pentru fiecare k: ∑i=1k di ≤ k(k−1) + ∑i=k+1n min(di, k)
Metoda practică (la BAC): Verifică dacă ∑di este pară și aplică algoritmul lui Hakimi (elimină nodul cu grad maxim, scade 1 din următorii dmax vecini).
Metoda practică (la BAC): Verifică dacă ∑di este pară și aplică algoritmul lui Hakimi (elimină nodul cu grad maxim, scade 1 din următorii dmax vecini).
📊 Formule de numărare
| Ce numărăm | Formula |
|---|---|
| Grafuri simple cu n noduri etichetate | 2n(n−1)/2 |
| Arbori etichetați cu n noduri (Cayley) | nn−2 |
| Grafuri conexe cu n noduri | Nu are formulă închisă simplă |
| Subgrafuri ale Kn | Alegeți submulțime V' și apoi muchii: 2n × 2|E| |
🎮
Demo interactiv — Construiește un graf
Click pe canvas pentru a adăuga noduri. Click pe două noduri pentru a adăuga o muchie. Observă formulele în timp real!
Noduri: 0 Muchii: 0 ∑grade: 0 Componente conexe: 0 Max muchii (Kn): 0 ✓ Eulerian
Experimentează:
- Adaugă 4 noduri și conectează-le pe toate → observă că K₄ are 6 muchii = 4×3/2
- Construiește un graf cu noduri de grad par → devine eulerian
- Rulează BFS/DFS pentru a vedea ordinea parcurgerii
🎓
Probleme tip BAC — Teoria Grafurilor
Problemă 1: Se dă un graf neorientat cu 6 noduri și 9 muchii. Care este suma gradelor tuturor nodurilor?
✅ Rezolvare
Aplicăm lema strângerii de mână: ∑d(v) = 2m = 2 × 9 = 18
Problemă 2: Câte muchii are graful complet K₇?
✅ Rezolvare
m = n(n−1)/2 = 7×6/2 = 21 muchii. Fiecare nod are gradul 6.
Problemă 3: Un graf neorientat conex cu 8 noduri are un ciclu eulerian. Dacă 6 noduri au gradul 4, iar celelalte 2 au grad egal, care este gradul lor?
✅ Rezolvare
Ciclu eulerian → toate gradele sunt pare (condiție îndeplinită automat).
∑d(v) = 2m → 6×4 + 2×d = 2m → ∑ trebuie să fie pară.
24 + 2d = 2m → d poate fi orice număr par ≥ 1.
Răspuns: d = 2 (minim posibil, par) → m = (24+4)/2 = 14 muchii, grad = 2.
Problemă 4: Un graf neorientat cu 5 noduri are matricea de adiacență cu a[1][2]=a[1][3]=a[2][4]=a[3][5]=a[4][5]=1 (simetric). Câte componente conexe are?
✅ Rezolvare
Muchii: (1,2), (1,3), (2,4), (3,5), (4,5). Pornim DFS din 1 → ajungem la 2→4→5→3 (toate).
Răspuns: 1 componentă conexă (graful este conex).
Problemă 5: Care este numărul minim de muchii care trebuie adăugate unui graf cu 5 noduri și 3 componente conexe pentru a-l face conex?
✅ Rezolvare
Pentru a face un graf conex din k componente, trebuie adăugate cel puțin k−1 muchii (le conectăm ca un lanț).
Răspuns: 3 − 1 = 2 muchii
💪