Invatare Atomica

Introducere Grafuri: Notiuni de Baza

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei intelege ce este un graf, cum se descrie matematic, ce sunt nodurile si muchiile, cum se calculeaza gradul unui nod, si vei distinge intre tipurile principale de grafuri (orientat, neorientat, complet, conex, bipartit).

Dupa aceasta lectie vei putea:

  • Sa definesti un graf ca pereche G = (V, E) si sa identifici nodurile si muchiile
  • Sa calculezi gradul unui nod si sa aplici Lema Mainilor (suma grade = 2|E|)
  • Sa distingi intre graf orientat si neorientat, grad interior si exterior
  • Sa identifici graful complet Kn, graful conex si graful bipartit
  • Sa implementezi reprezentarea unui graf si calculul de grade in Python
  • (Intensiv) Sa implementezi aceleasi operatii in C++ cu vector<pair<int,int>>

Incearca singur!

Provocare:

Gandeste-te la colegii tai din clasa. Daca trasezi o linie intre tine si fiecare coleg cu care colaborezi la proiecte, obtii un “graf de colaborare”. Cati colegi ai cu care colaborezi? Acesta este gradul nodului tau in acel graf.

💡 Ai nevoie de un indiciu?

In teoria grafurilor: tu esti un nod, fiecare coleg este un nod, iar fiecare legatura de colaborare este o muchie.

Gradul tau = numarul de muchii care pleaca din nodul tau = numarul de colegi cu care colaborezi direct.

1

1. Ce este un graf? Definitie formala

Un graf este o pereche ordonata G = (V, E) unde:
  • V — multimea varfurilor (nodurilor), V ≠ ∅
  • E — multimea muchiilor (legaturilor intre noduri); E ⊆ V × V

Scriem |V| = n (numarul de noduri) si |E| = m (numarul de muchii).
Exemple din viata reala:

Reteaua de drumuri intre orase: orasele = noduri, drumurile = muchii.

Reteaua de calculatoare: calculatoarele = noduri, cablurile de retea = muchii.

Orarul unui profesor: materiile = noduri, conflictele de timp = muchii.

In Python putem reprezenta un graf simplu cu doua seturi:

# Graf neorientat: G = (V, E)
V = {1, 2, 3, 4, 5}
E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)}

print("Noduri (V):", sorted(V))
print("Muchii (E):", sorted(E))
print("Numar noduri |V| =", len(V))
print("Numar muchii |E| =", len(E))
Output real (rulat cu python):
Noduri (V): [1, 2, 3, 4, 5]
Muchii (E): [(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
Numar noduri |V| = 5
Numar muchii |E| = 6
2

2. Gradul unui nod si Lema Mainilor

Gradul unui nod v (notat d(v) sau grad(v)) = numarul de muchii incidente cu v = numarul de vecini directi ai lui v.

Lema Mainilor (Handshaking Lemma):
∑ d(v) = 2 · |E|

Consecinta imediata: Numarul de noduri cu grad impar este intotdeauna par (nu poate exista un numar impar de noduri cu grad impar). 
# Calculul gradului fiecarui nod intr-un graf neorientat
muchii = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 5), (4, 5)]
noduri = [1, 2, 3, 4, 5]

grad = {}
for nod in noduri:
    grad[nod] = 0

for (u, v) in muchii:
    grad[u] += 1
    grad[v] += 1

print("Gradul fiecarui nod:")
for nod in noduri:
    print(f"  grad({nod}) = {grad[nod]}")

suma_grade = sum(grad.values())
print(f"\nSuma gradelor = {suma_grade}")
print(f"2 * |E| = {2 * len(muchii)}")
print("Lema mainilor: suma grade = 2 * numar muchii ->", suma_grade == 2 * len(muchii))
Output real (rulat cu python):
Gradul fiecarui nod:
  grad(1) = 2
  grad(2) = 3
  grad(3) = 3
  grad(4) = 2
  grad(5) = 2

Suma gradelor = 12
2 * |E| = 12
Lema mainilor: suma grade = 2 * numar muchii -> True
De retinut:

Nodurile 2 si 3 au grad 3 (gradul maxim in acest graf). Nodurile 1, 4, 5 au grad 2. Un nod cu grad 0 se numeste nod izolat. Complexitate calcul grade: O(|V| + |E|).

3

3. Graf orientat vs. Graf neorientat

Graf neorientat: Muchia (u, v) = (v, u): legatura bidirectionala. Nu conteaza ordinea.

Graf orientat (digraf): Arcul (u, v) ≠ (v, u): legatura unidirectionala, de la u la v.

In graful orientat distingem:
  • grad interior d−(v) = numarul arcelor care intra in v
  • grad exterior d+(v) = numarul arcelor care ies din v
Lema mainilor generalizata: ∑ d+(v) = ∑ d−(v) = |E| 
# Graf orientat (digraf): arcele au directie
arce = [(1, 2), (1, 3), (3, 2), (2, 4), (4, 3), (3, 5)]
noduri = [1, 2, 3, 4, 5]

grad_in  = {nod: 0 for nod in noduri}
grad_out = {nod: 0 for nod in noduri}

for (u, v) in arce:
    grad_out[u] += 1
    grad_in[v]  += 1

print("Gradul nodurilor in graful orientat:")
print(f"{'Nod':>4} | {'grad_out (exterior)':>20} | {'grad_in (interior)':>18}")
print("-" * 50)
for nod in noduri:
    print(f"{nod:>4} | {grad_out[nod]:>20} | {grad_in[nod]:>18}")
Output real (rulat cu python):
Gradul nodurilor in graful orientat:
 Nod |  grad_out (exterior) | grad_in (interior)
--------------------------------------------------
   1 |                    2 |                  0
   2 |                    1 |                  2
   3 |                    2 |                  2
   4 |                    1 |                  1
   5 |                    0 |                  1
Interpretare:

Nodul 1 are grad interior 0 (nicio sageata intra in el — este sursa). Nodul 5 are grad exterior 0 (nicio sageata iese din el — este destinatie/absorbtie).

4

4. Tipuri de grafuri: complet, conex, bipartit

Graf complet Kn: Orice doua noduri distincte sunt conectate direct. Are exact n·(n−1)/2 muchii. Fiecare nod are gradul n−1.

Graf conex: Intre orice doua noduri u si v exista cel putin un lant (secventa de noduri si muchii). Daca nu este conex, graful are mai multe componente conexe.

Graf bipartit: Nodurile se pot imparti in doua multimi disjuncte A si B astfel incat orice muchie are un capat in A si celalalt in B. Detectie: 2-colorare prin BFS (un graf este bipartit daca si numai daca nu are cicluri de lungime impara). 
# Verificare graf complet si bipartit

def este_complet(noduri, muchii):
    n = len(noduri)
    muchii_max = n * (n - 1) // 2
    return len(muchii) == muchii_max

def este_bipartit_simplu(noduri, muchii):
    culoare = {}
    adj = {nod: [] for nod in noduri}
    for (u, v) in muchii:
        adj[u].append(v)
        adj[v].append(u)
    for start in noduri:
        if start not in culoare:
            coada = [start]
            culoare[start] = 0
            while coada:
                nod = coada.pop(0)
                for vecin in adj[nod]:
                    if vecin not in culoare:
                        culoare[vecin] = 1 - culoare[nod]
                        coada.append(vecin)
                    elif culoare[vecin] == culoare[nod]:
                        return False
    return True

# Graf K4 (complet cu 4 noduri)
V4 = [1, 2, 3, 4]
E4 = [(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)]
print("Graf K4 (complet cu 4 noduri):")
print(f"  Noduri: {V4}, Muchii: {len(E4)}")
print(f"  Este complet? {este_complet(V4, E4)}")
print(f"  Este bipartit? {este_bipartit_simplu(V4, E4)}")
print()
# Graf bipartit: A={1,2}, B={3,4}
V_bip = [1, 2, 3, 4]
E_bip = [(1,3),(1,4),(2,3),(2,4)]
print("Graf bipartit: A={1,2}, B={3,4}")
print(f"  Muchii: {E_bip}")
print(f"  Este complet? {este_complet(V_bip, E_bip)}")
print(f"  Este bipartit? {este_bipartit_simplu(V_bip, E_bip)}")
Output real (rulat cu python):
Graf K4 (complet cu 4 noduri):
  Noduri: [1, 2, 3, 4], Muchii: 6
  Este complet? True
  Este bipartit? False

Graf bipartit: A={1,2}, B={3,4}
  Muchii: [(1, 3), (1, 4), (2, 3), (2, 4)]
  Este complet? False
  Este bipartit? True
5

5. Conexitate, lant, ciclu — verificare DFS

Lant: Secventa de noduri v0, v1, ..., vk in care oricare doua consecutive sunt legate printr-o muchie. Lungimea lantului = numarul de muchii = k.

Drum (in graf orientat): Secventa in care arcele respecta directia (de la vi la vi+1).

Ciclu: Lant cu v0 = vk (incepe si termina in acelasi nod). Lungime minima ciclu simplu = 3 (triunghi).

Graf aciclic: Nu contine niciun ciclu. Un graf neorientat conex si aciclic se numeste arbore (studiat in modulul urmator). 
# Verificare conexitate cu DFS iterativ

def este_conex(noduri, muchii):
    adj = {nod: [] for nod in noduri}
    for (u, v) in muchii:
        adj[u].append(v)
        adj[v].append(u)
    if not noduri:
        return True
    vizitat = set()
    stiva = [noduri[0]]
    vizitat.add(noduri[0])
    while stiva:
        nod = stiva.pop()
        for vecin in adj[nod]:
            if vecin not in vizitat:
                vizitat.add(vecin)
                stiva.append(vecin)
    return len(vizitat) == len(noduri)

# Graf conex
V1 = [1, 2, 3, 4, 5]
E1 = [(1,2),(2,3),(3,4),(4,5),(5,1),(2,4)]
print("Graf conex:")
print(f"  Noduri: {V1}")
print(f"  Muchii: {E1}")
print(f"  Este conex? {este_conex(V1, E1)}")
print()
# Graf neconex (nodul 4 este izolat)
V2 = [1, 2, 3, 4]
E2 = [(1,2),(2,3)]
print("Graf neconex (nodul 4 izolat):")
print(f"  Noduri: {V2}")
print(f"  Muchii: {E2}")
print(f"  Este conex? {este_conex(V2, E2)}")
Output real (rulat cu python):
Graf conex:
  Noduri: [1, 2, 3, 4, 5]
  Muchii: [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1), (2, 4)]
  Este conex? True

Graf neconex (nodul 4 izolat):
  Noduri: [1, 2, 3, 4]
  Muchii: [(1, 2), (2, 3)]
  Este conex? False
Complexitate:

Verificarea conexitatii prin DFS/BFS ruleaza in O(|V| + |E|) — liniar in numarul de noduri plus numarul de muchii.

6

6. Grafuri in C++ EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

La profilul intensiv implementam grafuri in C++ folosind vector<pair<int,int>> pentru lista de muchii si vector<int> pentru grade. Folosim structured bindings C++17 (auto& [u, v]) pentru iterare eleganta — evitam .first si .second.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // Graf neorientat: 5 noduri, lista de muchii
    int n = 5;
    vector<pair<int,int>> muchii = {
        {1,2},{1,3},{2,3},{2,4},{3,5},{4,5}
    };

    // Gradul fiecarui nod (indexat de la 1)
    vector<int> grad(n + 1, 0);
    for (auto& [u, v] : muchii) {
        grad[u]++;
        grad[v]++;
    }

    cout << "Graf neorientat cu " << n << " noduri si "
         << muchii.size() << " muchii" << endl;
    cout << "Gradele nodurilor:" << endl;
    for (int i = 1; i <= n; i++) {
        cout << "  grad(" << i << ") = " << grad[i] << endl;
    }

    int suma = 0;
    for (int i = 1; i <= n; i++) suma += grad[i];
    cout << "Suma grade = " << suma
         << " (= 2 * " << muchii.size() << " = "
         << 2 * (int)muchii.size() << ")" << endl;

    return 0;
}
Output real (compilat g++ -std=c++17, apoi rulat):
Graf neorientat cu 5 noduri si 6 muchii
Gradele nodurilor:
  grad(1) = 2
  grad(2) = 3
  grad(3) = 3
  grad(4) = 2
  grad(5) = 2
Suma grade = 12 (= 2 * 6 = 12)

Aceleasi rezultate ca in Python — acelasi algoritm O(|V| + |E|), doar sintaxa difera. In lectia urmatoare vom trece la reprezentari mai eficiente: matrice de adiacenta si liste de adiacenta.

Exercitii practice

Exercitiul 1 (Nivel minim) — Calcul grad

Se da graful neorientat cu nodurile {A, B, C, D, E} si muchiile {AB, AC, BC, BD, CE, DE}.

  1. Scrie multimile V si E cu notatia matematica G = (V, E).
  2. Calculeaza gradul fiecarui nod.
  3. Verifica Lema Mainilor: suma gradelor = 2 × numarul de muchii.
  4. Exista noduri izolate? Exista noduri cu grad impar? Cate?
Vezi rezolvarea

V si E: V = {A, B, C, D, E}, E = {AB, AC, BC, BD, CE, DE}. Graful G = (V, E) are |V| = 5 noduri si |E| = 6 muchii.

Gradele nodurilor (numaram muchiile incidente fiecarui nod):

  1. grad(A) = 2 (muchiile AB, AC)
  2. grad(B) = 3 (AB, BC, BD)
  3. grad(C) = 3 (AC, BC, CE)
  4. grad(D) = 2 (BD, DE)
  5. grad(E) = 2 (CE, DE)

Lema Mainilor: suma gradelor = 2+3+3+2+2 = 12, iar 2 x |E| = 2 x 6 = 12. Coincid, deci lema e verificata.

Noduri izolate: nu exista (toate au gradul cel putin 2). Noduri cu grad impar: B si C (grad 3 fiecare) — sunt 2 noduri, adica un numar par, exact cum spune consecinta lemei mainilor.

Exercitiul 2 (Nivel standard) — Graf orientat

Se da graful orientat G cu nodurile {1, 2, 3, 4} si arcele {(1,2), (1,3), (2,4), (3,2), (4,1), (4,3)}.

  1. Calculeaza gradul interior si exterior al fiecarui nod.
  2. Verifica: suma grad_in = suma grad_out = |E|.
  3. Identifica sursele (grad interior 0) si absorbtiile (grad exterior 0) din graf.
  4. Exista un ciclu orientat? Descrie-l ca secventa de noduri.
Vezi rezolvarea

Grad interior si exterior (numaram arcele care intra/pleaca din fiecare nod):

  1. nod 1: grad_out = 2 (arcele (1,2), (1,3)), grad_in = 1 (arcul (4,1))
  2. nod 2: grad_out = 1 ((2,4)), grad_in = 2 ((1,2), (3,2))
  3. nod 3: grad_out = 1 ((3,2)), grad_in = 2 ((1,3), (4,3))
  4. nod 4: grad_out = 2 ((4,1), (4,3)), grad_in = 1 ((2,4))

Verificare: suma grad_out = 2+1+1+2 = 6, suma grad_in = 1+2+2+1 = 6, si |E| = 6. Toate trei coincid.

Surse (grad interior 0): niciunul — fiecare nod are cel putin un arc care intra. Absorbtii (grad exterior 0): niciunul — fiecare nod are cel putin un arc care iese.

Ciclu orientat: 1 -> 2 -> 4 -> 1 (arcele (1,2), (2,4) si (4,1) exista toate in E, deci secventa se inchide).

Exercitiul 3 (Nivel performanta) — Analiza completa in Python

Construieste in Python un graf neorientat cu n = 6 noduri si muchiile {(1,2),(1,4),(2,3),(2,5),(3,6),(4,5),(5,6)}.

  1. Verifica daca graful este conex (folosind DFS iterativ).
  2. Gaseste toate tripletele de noduri (i, j, k) cu i < j < k care formeaza un triunghi (ciclu de lungime 3).
  3. Calculeaza numarul de componente conexe daca elimini nodul 2 si toate muchiile incidente lui.
  4. (Exclusiv intensiv C++) Rescrie verificarea conexitatii in C++ cu vector<vector<int>> pentru lista de adiacenta.
Vezi rezolvarea

Schita (nivel performanta — codul ramane de scris de tine):

  1. Conexitate: adj ca dictionar nod -> vecini, apoi reia este_conex din lectie (DFS iterativ cu stiva). DFS din 1 atinge toate cele 6 noduri -> graf conex.
  2. Triunghiuri (i<j<k): pentru fiecare muchie (i,j) cauta un k comun in adj[i] si adj[j]. Capcana: nu presupune ca exista unul — verifica toate 7 muchiile. Graful e un hexagon 1-2-3-6-5-4-1 plus coarda 2-5: rezulta doua patrulatere, deci raspunsul corect e multimea vida (niciun triunghi).
  3. Fara nodul 2: raman muchiile (1,4),(4,5),(5,6),(3,6) = lantul 1-4-5-6-3, tot conex -> 1 singura componenta.
  4. C++ (intensiv): vector<vector<int>> + DFS de conexitate NU apar in lectie (C++-ul predat calculeaza doar grade, cu vector<pair<int,int>>) — adapteaza singur structura Python.

Evaluare: conexitate corecta; triunghiuri corect identificate (inclusiv cazul fara niciunul); componente recalculate corect; C++ compileaza si da acelasi rezultat.

Ce ai invatat astazi

  • Definitia formala a grafului: G = (V, E), cu |V| = n noduri si |E| = m muchii
  • Gradul unui nod = numarul de muchii incidente; Lema Mainilor: ∑d(v) = 2|E|
  • Graf orientat vs. neorientat; grad interior d−(v) si grad exterior d+(v)
  • Graf complet Kn cu n·(n−1)/2 muchii; graf conex; graf bipartit (2-colorabil)
  • Lant, drum, ciclu; graf aciclic; conexitate verificata prin DFS in O(|V| + |E|)
  • (Intensiv) Implementare C++ cu vector<pair<int,int>> si structured bindings C++17

Vrei mai mult?

Provocare: Scrie o functie este_regulat(noduri, muchii) care verifica daca toate nodurile unui graf au acelasi grad. Testeaz-o pe graful complet K4 (nodurile {1,2,3,4}, toate muchiile posibile) - trebuie sa fie regulat, cu gradul 3 pentru fiecare nod - si pe graful din atomul 2 al lectiei, care NU e regulat.

De ce? Numarul de noduri cu grad impar dintr-un graf este intotdeauna PAR, niciodata impar. Foloseste Lema Mainilor (suma gradelor = 2|E|, deci mereu para) ca sa explici de ce nu poate exista un numar impar de noduri cu grad impar.

Deschidere: Reteaua de prieteni dintr-o retea sociala este un graf urias unde gradul unui nod = numarul de prieteni directi. Algoritmii de tip "persoane pe care poate le cunosti" cauta noduri la distanta 2 (prieteni ai prietenilor), folosind exact aceste notiuni de grad si vecinatate.

Urmatoarea lectie

Continua cu Lectia 6: Reprezentari grafuri — matrice de adiacenta, liste de adiacenta si comparatia complexitatii spatiale O(n2) vs O(n+m).

Continua →