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).

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) DA (toate grade = 3 — par); c) NU (grad(1)=1, grad(5)=1 — impare).

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.

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

Urmatoarea lectie

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

Continua →