Invatare Atomica

Lanturi, cicluri si drumuri intr-un graf

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei invata sa descrii si sa clasifici traseele intr-un graf (lanturi, cicluri, drumuri), sa recunosti tipurile elementare si vei vedea cum se verifica aceste proprietati in cod Python si in C++ (intensiv).

Dupa aceasta lectie vei putea:

  • Sa definesti corect un lant, un lant simplu si un lant elementar
  • Sa definesti un ciclu si un ciclu elementar
  • Sa distingi intre circuit eulerian si circuit hamiltonian
  • Sa definesti un drum si un circuit intr-un graf orientat
  • Sa calculezi lungimea unui lant / drum
  • Sa implementezi in Python verificarea unui lant elementar
  • Sa recunosti conditia Euler pentru existenta unui circuit eulerian

Incearca singur!

Provocare:

Imagineaza-ti un oras cu 5 intersectii si 5 strazi: 1-2, 2-3, 2-4, 3-4, 4-5. Poti gasi un traseu care trece prin FIECARE strada exact o singura data si se intoarce la start? Dar un traseu care trece prin FIECARE intersectie exact o singura data?

💡 Ai nevoie de un indiciu?

Traseul prin fiecare strada (muchie) o singura data = lant eulerian. Exista circuit eulerian daca toate intersectiile au grad par. Traseul prin fiecare intersectie o singura data = lant hamiltonian. Nu exista formula simpla pentru asta!

1

1. Graful de lucru si definitia lantului

In aceasta lectie lucram cu graful neorientat G = (V, E):
V = {1, 2, 3, 4, 5}    E = {(1,2), (2,3), (2,4), (3,4), (4,5)}
Lista de adiacenta a grafului G:
1: [2]
2: [1, 3, 4]
3: [2, 4]
4: [2, 3, 5]
5: [4]

Gradele nodurilor: grad(1)=1, grad(2)=3, grad(3)=2, grad(4)=3, grad(5)=1

Definitie — Lant: O secventa de noduri v0, v1, ..., vk astfel incat (vi, vi+1) ∈ E pentru orice i.
Lungimea = numarul de muchii = k.
Exemple:
L = [1, 2, 4, 3]  → lant de lungime 3 (muchii: 1-2, 2-4, 4-3)
S = [1, 2, 5]     → NU e lant (muchia 2-5 nu exista in G)

Proprietate: suma gradelor = 2 × numarul de muchii.

# Verificare: suma gradelor = 2 * nr_muchii
G = {1:[2], 2:[1,3,4], 3:[2,4], 4:[2,3,5], 5:[4]}
suma = sum(len(G[n]) for n in G)
print(f"Suma gradelor: {suma}")
print(f"Numar muchii: {suma // 2}")
lant = [1, 2, 4, 3]
print(f"Lungimea lantului {lant}: {len(lant) - 1}")
Output real (rulat cu python):
Suma gradelor: 10
Numar muchii: 5
Lungimea lantului [1, 2, 4, 3]: 3
2

2. Lant simplu si lant elementar — definitii si cod

  • Lant simplu: fiecare muchie apare cel mult o data
  • Lant elementar: fiecare nod apare cel mult o data (implica simplu)
Ierarhie: elementar ⊆ simplu ⊆ lant
Clasificare pe graful G:
L1 = [1, 2, 3, 4]    → elementar (noduri distincte, toate muchii existente)
L2 = [1, 2, 4, 3]    → elementar
L3 = [1, 2, 3, 2, 4] → lant; simplu? NU (muchia 2-3 repetat); elementar? NU
L4 = [1, 2, 5]       → NU e lant (muchia 2-5 lipseste)
def este_lant_elementar(G, secventa):
    # Verifica ca nu se repeta noduri
    if len(secventa) != len(set(secventa)):
        return False
    # Verifica ca exista muchie intre noduri consecutive
    for i in range(len(secventa) - 1):
        u, v = secventa[i], secventa[i+1]
        if v not in G[u]:
            return False
    return True

lant = [1, 2, 4, 3]
print(f"Lant: {lant}")
print(f"Lungime: {len(lant) - 1}")
print(f"Este lant elementar: {este_lant_elementar(G, lant)}")
lant2 = [1, 2, 3, 2, 4]
print(f"Lant: {lant2}")
print(f"Este lant elementar: {este_lant_elementar(G, lant2)}")
Output real (rulat cu python):
Lant: [1, 2, 4, 3]
Lungime: 3
Este lant elementar: True
Lant: [1, 2, 3, 2, 4]
Este lant elementar: False

Complexitate: O(n × d) unde n = lungimea secventei, d = gradul maxim al nodurilor.

3

3. Cicluri in graful neorientat

Ciclu: lant cu v0 = vk, k ≥ 1.
Ciclu simplu: muchiile nu se repeta.
Ciclu elementar: nodurile interioare distincte si diferite de v0. Lungime minima: 3.
Cicluri in G (cu muchia aditionala 1-5):
C1 = [1, 2, 3, 4, 5, 1] → ciclu elementar, lungime 5
C2 = [2, 3, 4, 2]       → ciclu elementar, lungime 3
C3 = [2, 4, 3, 2]       → ciclu elementar, lungime 3 (sens invers)
# Graful G extins cu muchia 1-5
G2 = {1:[2,5], 2:[1,3,4], 3:[2,4], 4:[2,3,5], 5:[1,4]}

def este_ciclu_elementar(G, s):
    if len(s) < 3: return False
    if s[0] != s[-1]: return False
    interior = s[:-1]
    if len(interior) != len(set(interior)): return False
    for i in range(len(interior) - 1):
        if interior[i+1] not in G[interior[i]]: return False
    if interior[0] not in G[interior[-1]]: return False
    return True

c1 = [1,2,3,4,5,1]
c2 = [2,3,4,2]
print(f"C1={c1}: ciclu elementar={este_ciclu_elementar(G2,c1)}")
print(f"C2={c2}: ciclu elementar={este_ciclu_elementar(G2,c2)}")
Output real (rulat cu python):
C1=[1, 2, 3, 4, 5, 1]: ciclu elementar=True
C2=[2, 3, 4, 2]: ciclu elementar=True
4

4. Circuit eulerian si circuit hamiltonian

Lant eulerian: trece prin fiecare muchie exact o data.
Circuit eulerian: lant eulerian inchis.
Teorema Euler (1736): Graf conex are circuit eulerian ⇔ toate gradele sunt pare.

Lant hamiltonian: trece prin fiecare nod exact o data.
Circuit hamiltonian: lant hamiltonian inchis.
Atentie: nu exista conditie simpla — problema este NP-completa. 
def grad(G, nod): return len(G[nod])

def are_circuit_eulerian(G):
    for nod in G:
        if grad(G, nod) % 2 != 0:
            return False
    return True

G1 = {1:[2,3], 2:[1,3], 3:[1,2]}
G2 = {1:[2,3,4], 2:[1,3], 3:[1,2,4], 4:[1,3]}
print(f"G1 graduri: {[grad(G1,n) for n in G1]}")
print(f"G1 circuit eulerian: {are_circuit_eulerian(G1)}")
print(f"G2 graduri: {[grad(G2,n) for n in G2]}")
print(f"G2 circuit eulerian: {are_circuit_eulerian(G2)}")
Output real (rulat cu python):
G1 graduri: [2, 2, 2]
G1 circuit eulerian: True
G2 graduri: [3, 2, 3, 2]
G2 circuit eulerian: False

Circuit hamiltonian prin backtracking (K4):

GH = {1:[2,3,4], 2:[1,3,4], 3:[1,2,4], 4:[1,2,3]}; n=4

def hamiltonian(G, nod, vizitat, drum, n):
    if len(drum) == n: return drum[0] in G[drum[-1]]
    for vecin in G[nod]:
        if vecin not in vizitat:
            vizitat.add(vecin); drum.append(vecin)
            if hamiltonian(G, vecin, vizitat, drum, n): return True
            drum.pop(); vizitat.remove(vecin)
    return False

drum=[1]; vizitat={1}
if hamiltonian(GH,1,vizitat,drum,n):
    drum.append(drum[0]); print(f"Circuit hamiltonian: {drum}")
Output real (rulat cu python):
Circuit hamiltonian: [1, 2, 3, 4, 1]
5

5. Drumuri si circuite in graful orientat

Intr-un graf orientat (digraf), arcul (u,v) merge doar de la u la v.
Drum: secventa v0,...,vk cu arcul (vi,vi+1) in digraf pentru orice i.
Drum elementar: nodurile sunt distincte.
Circuit: drum inchis (v0=vk).
Digraful GO: arce 1->2, 1->3, 2->4, 3->4, 3->5, 4->5
GO = {1:[2,3], 2:[4], 3:[4,5], 4:[5], 5:[]}
# Digraf - lista de succesori
GO = {1:[2,3], 2:[4], 3:[4,5], 4:[5], 5:[]}

def este_drum_elementar(GO, s):
    if len(s) != len(set(s)): return False
    for i in range(len(s) - 1):
        if s[i+1] not in GO[s[i]]: return False
    return True

d1=[1,2,4,5]; d2=[1,3,5]; d3=[1,2,3,5]
print(f"D1={d1}: drum elementar={este_drum_elementar(GO,d1)}")
print(f"D2={d2}: drum elementar={este_drum_elementar(GO,d2)}")
print(f"D3={d3}: drum elementar={este_drum_elementar(GO,d3)}")
Output real (rulat cu python):
D1=[1, 2, 4, 5]: drum elementar=True
D2=[1, 3, 5]: drum elementar=True
D3=[1, 2, 3, 5]: drum elementar=False
6

6. Implementare C++ cu liste de adiacenta EXCLUSIV INTENSIV

⚡ Sectiune doar pentru intensiv informatica

In C++ folosim vector<int> G[NMAX] pentru lista de adiacenta. Logica este identica cu Python; diferentele sunt tipuri explicite, iteratori STL si set<int> pentru noduri unice.

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

vector<int> G[6] = {
    {},                     // 0 neutilizat
    {2},                   // nod 1
    {1,3,4},             // nod 2
    {2,4},               // nod 3
    {2,3,5},             // nod 4
    {4}                   // nod 5
};

bool existaMuchie(int u, int v) {
    for (int x : G[u])
        if (x == v) return true;
    return false;
}

bool esteLantElementar(vector<int>& s) {
    set<int> vazut(s.begin(), s.end());
    if ((int)vazut.size() != (int)s.size()) return false;
    for (int i=0; i<(int)s.size()-1; i++)
        if (!existaMuchie(s[i],s[i+1])) return false;
    return true;
}

int main() {
    vector<int> l1={1,2,4,3}, l2={1,2,3,2,4};
    cout<<"Lant [1,2,4,3] elementar: "<<(esteLantElementar(l1)?"DA":"NU")<<endl;
    cout<<"Lungime: "<<l1.size()-1<<endl;
    cout<<"Lant [1,2,3,2,4] elementar: "<<(esteLantElementar(l2)?"DA":"NU")<<endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Lant [1,2,4,3] elementar: DA
Lungime: 3
Lant [1,2,3,2,4] elementar: NU

Aceeasi logica in Python si C++ — structura algoritmului nu depinde de limbaj.

Exercitii practice

Exercitiul 1 (Nivel minim) — Clasifica secventele

Fie G = {1:[2], 2:[1,3,4], 3:[2,4], 4:[2,3,5], 5:[4]}. Clasifica fiecare secventa (lant / nu-e-lant; simplu; elementar):

  • a) [1, 2, 4, 5]
  • b) [1, 2, 3, 4, 2]
  • c) [3, 4, 2, 1]
  • d) [1, 3, 4]

Raspuns: a) lant elementar (lung. 3); b) lant simplu, NU elementar (nodul 2 repetat); c) lant elementar (lung. 3); d) NU e lant (muchia 1-3 nu exista).

Vezi rezolvarea

Verific fiecare secventa: nodurile consecutive trebuie sa aiba muchie in G, iar pentru elementar toate nodurile trebuie sa fie distincte.

  1. a) [1, 2, 4, 5]: muchiile 1-2, 2-4, 4-5 exista toate; nodurile 1, 2, 4, 5 sunt distincte, deci este lant elementar, lungime 3.
  2. b) [1, 2, 3, 4, 2]: muchiile 1-2, 2-3, 3-4, 4-2 exista toate (este lant); toate muchiile folosite sunt diferite, deci este lant simplu; dar nodul 2 apare de doua ori, deci NU este elementar.
  3. c) [3, 4, 2, 1]: muchiile 3-4, 4-2, 2-1 exista toate; nodurile 3, 4, 2, 1 sunt distincte, deci este lant elementar, lungime 3.
  4. d) [1, 3, 4]: muchia 1-3 NU exista in G (nodul 1 este legat doar de nodul 2), deci secventa NU este lant.

Exercitiul 2 (Nivel standard) — Conditia Euler

Determina daca urmatoarele grafuri au circuit eulerian si justifica prin gradele nodurilor:

  • a) C4: {(1,2),(2,3),(3,4),(4,1)}
  • b) K4 (complet, 4 noduri)
  • c) Graful G din lectie (5 noduri, 5 muchii)

Indiciu: a) DA (toate grade = 2); b) NU (toate cele 4 noduri au grad 3 — impar, deci conditia Euler nu e indeplinita); c) NU (grad(1)=1, grad(5)=1 — impare).

Vezi rezolvarea

Aplic Teorema lui Euler (Atomul 4): un graf conex are circuit eulerian daca si numai daca toate nodurile au grad par.

  1. a) C4 = (1,2),(2,3),(3,4),(4,1): fiecare nod are exact 2 muchii, deci toate gradele sunt 2 (par); graful este conex (formeaza un ciclu), deci DA, are circuit eulerian.
  2. b) K4 (complet, 4 noduri): fiecare nod este legat de celelalte 3 noduri, deci grad 3 pentru toate (impar), deci NU, conditia Euler nu este indeplinita.
  3. c) Graful G din lectie: grad(1)=1, grad(2)=3, grad(3)=2, grad(4)=3, grad(5)=1. Nodurile 1, 2, 4, 5 au grad impar, deci NU are circuit eulerian.

Regula practica: este suficient un singur nod cu grad impar ca circuitul eulerian sa nu existe.

Exercitiul 3 (Nivel performanta) — Toate lanturile elementare

Scrie o functie Python care gaseste toate lanturile elementare de la nodul 1 la nodul 5 in G, folosind backtracking. Afiseaza lanturile si lungimile lor.

Rezultat asteptat: [1,2,4,5] (lung. 3) si [1,2,3,4,5] (lung. 4) — doua lanturi elementare distincte.

Vezi rezolvarea

Nu dau codul complet — doar schita de rezolvare, pe baza modelului din Atomul 2 (este_lant_elementar):

  1. Functia primeste graful G, nodul curent, nodul tinta, drumul curent (lista) si o multime de noduri deja folosite pe acest drum.
  2. Daca nodul curent este egal cu tinta: salveaza o copie a drumului curent in lista de rezultate (nu referinta directa).
  3. Altfel: pentru fiecare vecin din G[curent] care NU este deja pe drum, adauga-l in drum, cheama functia recursiv, apoi scoate-l din drum (pasul de backtracking — fara el se pierd solutiile).
  4. Apelul initial porneste cu drumul [1].

Capcane: uitarea pasului de backtracking; salvarea drumului prin referinta in loc de copie (list(drum)). Rezultat corect, verificabil manual pornind din 1 (singurul sau vecin este 2): [1,2,4,5] (lungime 3) si [1,2,3,4,5] (lungime 4) — exact doua drumuri elementare.

Criterii de evaluare: gaseste exact aceste doua drumuri fara duplicate, foloseste corect adaugare/eliminare in backtracking, afiseaza si lungimea fiecarui drum (numar de muchii).

Ce ai invatat astazi

  • Lant = secventa noduri cu muchii consecutive existente; lungime = numarul de muchii
  • Lant simplu: muchii neduplicate; lant elementar: noduri neduplicate (implica simplu)
  • Ciclu = lant inchis; ciclu elementar: noduri interioare distincte; lungime minima 3
  • Circuit eulerian: trece prin fiecare muchie exact o data — exista ⇔ toate gradele pare (Euler, 1736)
  • Circuit hamiltonian: trece prin fiecare nod exact o data — NP-complet, fara conditie simpla
  • Drum / circuit in graful orientat: arcele au directie obligatorie
  • Verificare lant elementar: O(n × d) cu lista de adiacenta

Vrei mai mult?

Provocare: Ia graful G2 din Atomul 3 (cu muchia 1-5 adaugata): G2 = {1:[2,5], 2:[1,3,4], 3:[2,4], 4:[2,3,5], 5:[1,4]}. Scrie in Python o functie care testeaza toate permutarile celor 5 noduri cu itertools.permutations si verifica daca vreuna formeaza un circuit hamiltonian (trece prin fiecare nod o singura data si se inchide). Ruleaza codul si scrie exact ce gaseste.

De ce? Conditia lui Euler (toate gradele pare) se verifica in O(V). Pentru circuitul hamiltonian nu exista nicio conditie la fel de simpla, doar cautare exhaustiva. De ce crezi ca simpla numarare a gradelor e suficienta pentru Euler, dar nu exista o numarare echivalenta pentru Hamilton?

Dincolo de lectie: Problema podurilor din Konigsberg (Euler, 1736) e originea teoriei grafurilor. Circuitul hamiltonian sta in spatele problemei comisionarului voiajor (TSP), folosita de firmele de curierat pentru optimizarea rutelor de livrare.

Urmatoarea lectie

Continua cu parcurgerea DFS (Depth-First Search) — algoritmul fundamental de explorare in adancime a unui graf.

Continua →