Grafuri orientate (sortare topologica, drumuri, circuite)

Un graf orientat (digraf) este o pereche (V, A), unde V este o multime finita de noduri (varfuri), iar A este o multime de arce, fiecare arc fiind o pereche ordonata (u, v) care indica o directie de la u la v. Fata de grafurile neorientate, orientarea introduce notiuni specifice: gradul interior (numarul de arce care intra intr-un nod) si gradul exterior (numarul de arce care ies). Un drum intr-un graf orientat este o succesiune de noduri v1, v2, ..., vk astfel incat (vi, vi+1) ∈ A pentru orice i.

Lungimea unui drum se masoara in numarul de arce. Un circuit (sau ciclu orientat) este un drum care incepe si se termina in acelasi nod, fara a repeta alte noduri (cu exceptia primului si ultimului). Sortarea topologica este o ordonare liniara a nodurilor unui graf orientat aciclic (DAG) astfel incat pentru orice arc (u, v), nodul u apare inaintea lui v.

Algoritmul clasic de sortare topologica foloseste o coada (BFS) si se bazeaza pe stergerea repetata a nodurilor cu grad interior 0. Pentru detectarea circuitelor, se poate utiliza o parcurgere DFS cu marcarea nodurilor in starea: nevizitat, in curs de vizitare (pe stiva de apel) si finalizat; daca se intalneste un arc catre un nod „in curs”, graful contine un circuit. In context Bacalaureat, problemele tipice implica: construirea unui graf orientat, verificarea existentei unui drum intre doua noduri (folosind DFS sau BFS), determinarea numarului de drumuri de la un nod sursa la un nod destinatie (prin programare dinamica pe DAG), identificarea componentelor tare conexe (cu algoritmul lui Kosaraju sau Tarjan) si sortarea topologica.

De asemenea, se studiaza matricea de adiacenta si listele de adiacenta ca metode de reprezentare. O aplicatie importanta este planificarea sarcinilor: fiecare arc (i, j) indica faptul ca i trebuie executat inainte de j, iar sortarea topologica ofera o ordine valida. In cazul existentei unui circuit, nu se poate realiza o planificare liniara.

La examen, se cer algoritmi eficienti O(n+m) pentru grafuri cu n noduri si m arce.

Exemple

• Exemplul 1: Sortare topologica. Fie graful orientat cu nodurile {0,1,2,3} si arcele (0,1), (0,2), (1,3), (2,3). Grade interioare: 0->0, 1->1, 2->1, 3->2. Pas 1: nodul 0 (grad 0) se adauga in coada. Se scoate 0, se scad gradele nodurilor 1 si 2. Grade: 1->0, 2->0, 3->2. Pas 2: nodurile 1 si 2 au grad 0, se adauga (sa zicem 1). Se scoate 1, se scade gradul lui 3 (devine 1). Pas 3: nodul 2 (grad 0) se scoate, se scade gradul lui 3 (devine 0). Pas 4: nodul 3 se scoate. Ordonarea topologica obtinuta: 0,1,2,3. Se verifica: arcul (0,1) – 0 inaintea lui 1, corect; (2,3) – 2 inaintea lui 3, corect.
• Exemplul 2: Detectare circuit cu DFS. Fie graful cu nodurile {A,B,C} si arcele (A,B), (B,C), (C,A). Se porneste DFS din A: marcam A ca in curs (gri). Se merge la B (marcat gri), apoi la C (gri). Din C se incearca arcul catre A, care este deja gri → circuit detectat. Daca graful ar fi avut doar (A,B) si (B,C) (fara arcul C->A), atunci C nu ar mai avea vecini, s-ar marca finalizat (negru), apoi B finalizat, apoi A finalizat – fara circuit.
• Exemplul 3: Numarul de drumuri de la 0 la 3 intr-un DAG. Fie arcele (0,1), (0,2), (1,3), (2,3), (1,2). Se utilizeaza programare dinamica: dp[0]=1; parcurgem nodurile in ordine topologica (0,1,2,3). Pentru fiecare nod u, pentru fiecare vecin v: dp[v] += dp[u]. Astfel: dp[1] = dp[0] = 1; dp[2] = dp[0] + dp[1] = 1+1=2; dp[3] = dp[1] + dp[2] = 1+2=3. Exista 3 drumuri distincte: 0-1-3, 0-2-3, 0-1-2-3.

Concepte cheie: Graf orientat, Sortare topologica (algoritmul lui Kahn), Detectare circuite (DFS cu culori), Drumuri in DAG (programare dinamica), Grade interioare si exterioare, Reprezentare matrice/liste de adiacenta