Grafuri orientate (drumuri, sortare topologica, componente tare conexe)

Grafurile orientate (digrafuri) sunt definite ca perechi (V, E), unde V este mulțimea nodurilor (vârfurilor), iar E este mulțimea arcelor (muchii orientate). Fiecare arc este o pereche ordonată (u, v), indicând o direcție de la u la v. În contextul liceului (clasele 9-12) și al Bacalaureatului, studiul grafurilor orientate se concentrează pe trei concepte fundamentale: drumuri, sortare topologică și componente tare conexe.

Un drum într-un graf orientat este o succesiune de noduri (v0, v1, ..., vk) astfel încât (v_i, v_{i+1}) ∈ E pentru orice i. Un drum poate fi simplu (toate nodurile distincte) sau elementar (fără repetiții). Lungimea unui drum este numărul de arce parcurse.

Un drum care începe și se termină în același nod se numește circuit (sau ciclu orientat). Algoritmul lui Moore (BFS) poate fi folosit pentru a determina cel mai scurt drum în număr de arce, iar algoritmul lui Dijkstra (cu ponderi nenegative) pentru distanțe minime în grafuri ponderate.

Sortarea topologică se aplică grafurilor orientate aciclice (DAG - Directed Acyclic Graph). O sortare topologică este o ordonare liniară a nodurilor astfel încât, pentru orice arc (u, v), nodul u apare înaintea lui v în ordonare. Algoritmul clasic folosește o stivă și o parcurgere DFS (depth-first search): se vizitează fiecare nod, după ce se termină explorarea vecinilor, se adaugă nodul în stivă; la final, se afișează nodurile în ordinea inversă a adăugării.

O altă metodă este algoritmul lui Kahn, bazat pe grade de intrare: se elimină repetat nodurile cu grad interior 0.

Componentele tare conexe (CTC sau SCC - Strongly Connected Components) sunt subgrafuri maximale în care orice nod este accesibil din orice alt nod al aceleiași componente, prin drumuri orientate. Algoritmul lui Kosaraju (bazat pe două DFS-uri, prima pe graful original și a doua pe graful transpus) și algoritmul lui Tarjan (bazat pe o singură DFS și indici de timp) sunt cei mai cunoscuți. Identificarea CTC-urilor este utilă în optimizarea algoritmilor, analiza dependențelor și reducerea grafurilor orientate la DAG-uri (graful componentelor tare conexe).

În problemele de Bacalaureat, se cere adesea să se determine dacă un drum există între două noduri, să se realizeze o sortare topologică pentru un DAG, sau să se numere componentele tare conexe și să se afișeze nodurile care le compun. Înțelegerea acestor concepte și a algoritmilor asociați este esențială pentru promovarea examenului.

Exemple

• Exemplul 1: Fie graful orientat cu nodurile {1,2,3,4} și arcele (1,2), (1,3), (2,4), (3,4). Se cere să se determine cel mai scurt drum de la nodul 1 la nodul 4. Soluție: Aplicăm DFS/BFS (deși BFS este mai potrivit pentru distanțe minime neponderate). Pornind din 1, drumurile posibile: 1→2→4 (lungime 2), 1→3→4 (lungime 2). Deci distanța minimă este 2, iar drumurile sunt 1-2-4 și 1-3-4.
• Exemplul 2: Se dă graful orientat cu nodurile {A, B, C, D, E} și arcele (A,B), (A,C), (B,D), (C,D), (D,E), (E,C). Observăm că există un ciclu (C→D→E→C), deci graful nu este DAG. Nu se poate realiza o sortare topologică. Dacă eliminăm arcul (E,C), graful devine DAG. O sortare topologică posibilă: A, B, C, D, E (verificare: A→B, A→C, B→D, C→D, D→E – toate respectă ordinea).
• Exemplul 3: Fie graful orientat cu nodurile {1,2,3,4,5,6} și arcele (1,2), (2,1), (2,3), (3,2), (3,4), (4,5), (5,4), (5,6), (6,5). Aplicăm algoritmul lui Kosaraju: 1) DFS pe graful original: ordinea de finalizare poate fi 1,2,3,4,5,6. 2) Construim graful transpus (inversăm arcele). 3) Parcurgem nodurile în ordinea inversă a finalizării (de la ultimul finalizat la primul) și marcăm componentele. Rezultă componentele tare conexe: {1,2}, {3}, {4,5}, {6} (verificare: 1↔2, 4↔5 sunt tare conexe; 3 are arc doar la 2 și de la 2, dar nu există drum de la 3 la 2 invers, deci singur; 6 similar).

Concepte cheie: Drum orientat și lungimea acestuia, Sortare topologică (BFS-Kahn și DFS-stivă), Componente tare conexe (Kosaraju, Tarjan), Graf orientat aciclic (DAG), Grad interior și grad exterior, Algoritmi de parcurgere (DFS, BFS) în grafuri orientate