Pe scurt
Un graf orientat (digraf) este o pereche G=(V, A) cu arce direcționate, permițând modelarea dependențelor și fluxurilor. Sortarea topologică ordonează liniar nodurile unui graf aciclic (DAG) astfel încât arcele să meargă doar înainte, iar detectarea circuitelor este esențială pentru verificarea aciclicității. Algoritmii principali sunt Kahn (bazat pe grad intern) și DFS post-ordine, iar numărarea drumurilor într-un DAG se face eficient prin programare dinamică.
Definiția și proprietățile grafurilor orientate
Un
graf orientat (digraf) este o pereche
G=(V, A), unde:
- V este mulțimea nodurilor (vârfurilor)
- A este mulțimea arcelor (muchii orientate), fiecare arc fiind o pereche ordonată (u, v)
În grafurile orientate, relațiile sunt direcționate, ceea ce permite modelarea unor probleme precum:
- Dependențe între taskuri
- Fluxuri de date
- Rețele de transport
Sortarea topologică
Sortarea topologică este o ordonare liniară a nodurilor unui graf orientat aciclic (DAG – Directed Acyclic Graph), astfel încât pentru orice arc (u, v), nodul u apare înaintea lui v.
Algoritmul Kahn (bazat pe gradul intern)
- Se calculează gradul intern al fiecărui nod
- Se elimină nodurile cu grad intern 0 și se adaugă în ordine
- Se decrementează gradele interne ale vecinilor
Algoritmul DFS post-ordine
- Se realizează o parcurgere în adâncime
- Se adaugă nodurile la finalul explorării
Exemplu: Graful cu noduri {1,2,3,4,5} și arce (1→2), (1→3), (2→4), (3→4), (4→5)
- Grade interne: nod1=0, nod2=1, nod3=1, nod4=2, nod5=1
- Aplicând Kahn: coadă inițială [1] → se scoate 1, se decrementează gradele pentru 2 și 3 (devin 0) → se adaugă 2 și 3
- Se continuă până la ordonarea finală: 1, 2, 3, 4, 5 (sau 1, 3, 2, 4, 5)
Drumuri și circuite în grafuri orientate
Un
drum într-un graf orientat este o succesiune de noduri
(v₁, v₂, …, vₖ) cu arce
(v_i, v_{i+1}) pentru fiecare
i.
Lungimea drumului este numărul de arce.
Un circuit (sau ciclu orientat) este un drum închis, unde v₁ = vₖ, iar k ≥ 2.
Detectarea circuitelor
Detecția circuitelor este crucială pentru a verifica dacă un graf este aciclic (DAG).
Metoda DFS cu culori
- Dacă în timpul unui DFS se găsește un arc întâlnind un nod aflat în curs de explorare (culoare gri), există un circuit
Metoda sortării topologice
- Dacă nu se pot ordona toate nodurile (rămân noduri cu grad intern > 0), graful are circuit
Exemplu: Graful cu nodurile {A, B, C} și arcele (A→B), (B→C), (C→A)
- DFS: plecăm din A, vizităm B, apoi C, încercăm să mergem la A, dar A este în stiva de explorare → circuit
- Sortare topologică: grade interne: A=1, B=1, C=1, niciun nod cu grad 0 → există circuit
Numărarea drumurilor într-un DAG
Numărarea drumurilor între două noduri se face prin
programare dinamică după sortarea topologică.
Exemplu: Graful cu noduri 1..6, arce: 1→2, 1→3, 2→4, 3→4, 4→5, 5→6, 2→6
- Sortare topologică: 1, 2, 3, 4, 5, 6
- Programare dinamică: dp[1]=1
- Parcurgem în ordinea sortată și actualizăm vecinii
- Rezultat: 3 drumuri de la 1 la 6
Aplicații tipice
- Planificarea proiectelor
- Compilare (ordinea instrucțiunilor)
- Gestionarea dependențelor
Concepte cheie pentru Bacalaureat
- Sortare topologică (algoritmul Kahn, DFS post-ordine)
- Detectarea circuitelor (culori DFS, grad intern)
- Drumuri și circuite în grafuri orientate
- Aplicații: dependențe, planificare, compilare
- Numărarea drumurilor într-un DAG folosind programare dinamică
Verifică-te!
- Care sunt cele două metode principale de realizare a sortării topologice și pe ce principiu se bazează fiecare?
- Cum poți detecta existența unui circuit într-un graf orientat folosind algoritmul de sortare topologică?
- Ce proprietate trebuie să aibă un graf orientat pentru a putea aplica numărarea drumurilor prin programare dinamică?