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?

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.

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.

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

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 →