Graf orientat

Ce este

Un graf orientat (sau digraf) este o pereche G = (V, U), unde V este o mulțime finită de noduri (vârfuri), iar U este o mulțime de arce. Un arc este o pereche ordonată (u, v) de noduri distincte:

• u se numește extremitatea inițială a arcului — de aici pleacă săgeata;
• v se numește extremitatea finală — aici intră săgeata;
• spunem că v este succesor al lui u, iar u este predecesor al lui v.

Compară cu graful neorientat, pe care îl știi deja:

• La graful neorientat, o muchie este o pereche neordonată [u, v]: scrierea [u, v] și [v, u] înseamnă exact aceeași muchie, iar parcurgerea e permisă în ambele sensuri.
• La graful orientat, arcul (u, v) este o pereche ordonată: există o săgeată u → v și atât. (u, v) și (v, u) sunt două arce diferite.

Cu alte cuvinte, arcul (u, v) îți dă voie să mergi din u în v, dar nu și din v în u. Drumul invers există doar dacă graful conține și arcul (v, u).

Cum arată

Pornește vizualizarea de mai jos și urmărește cum se adaugă pe rând arcele. Observă săgeata de pe fiecare legătură: ea pleacă din extremitatea inițială și intră în extremitatea finală. Spre deosebire de graful neorientat, aici sensul nu e niciodată reciproc decât dacă apar explicit ambele arce.

Să fixăm ideea pe un exemplu concret: un graf orientat cu 4 noduri și arcele (1,2), (2,3), (3,1), (1,4). Iată ce înseamnă fiecare arc, ca săgeată:

Dacă pornim din nodul 1 și urmăm doar săgețile, putem face 1 → 2 → 3 → 1 (un circuit care ne aduce înapoi) sau 1 → 4 (de unde nu mai pleacă nicio săgeată). Reține: deși există arcul (1,2), nu poți merge 2 → 1 direct, fiindcă arcul (2, 1) nu există.

Lista de adiacență a fiecărui nod conține doar succesorii lui — destinațiile arcelor care pleacă din el. Sub fiecare nod scriem unde poți ajunge direct:

Observă că 4 apare în lista lui 1 (din arcul (1,4)), dar 1 nu apare în lista lui 4 — pentru că arcul (4, 1) nu există. Lista nu mai e simetrică, ca la graful neorientat.

Grad intern și grad extern

La graful neorientat, un nod avea un singur grad. Aici săgețile au sens, deci fiecare nod primește două numere:

• gradul extern d⁺(u) = numărul arcelor care pleacă din u (câte noduri sunt succesori ai lui u);
• gradul intern d⁻(u) = numărul arcelor care intră în u (câți predecesori are u).

Pe exemplul nostru cu arcele (1,2), (2,3), (3,1), (1,4):

Verifică pe coloane: suma gradelor externe este 2 + 1 + 1 + 0 = 4, iar suma gradelor interne este 1 + 1 + 1 + 1 = 4 — exact m, numărul de arce. Nu e o coincidență: fiecare arc pleacă dintr-un singur nod și intră într-un singur nod, deci contribuie cu exact 1 la fiecare sumă. La graful neorientat suma gradelor era 2m; aici cele două sume sunt fiecare egale cu m. Această verificare rapidă prinde multe greșeli de citire la concurs.

Implementare C++

Construim lista de adiacență și, din mers, cele două grade. Singura schimbare față de graful neorientat: pentru arcul (u, v) adăugăm doar v în adj[u], nu și invers.

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

int main() {
    int n = 4, m = 4;
    // arcele (u, v): pleaca din u (extremitate initiala),
    // intra in v (extremitate finala)
    int arce[4][2] = {{1, 2}, {2, 3}, {3, 1}, {1, 4}};

    vector<int> adj[5];        // adj[u] = succesorii lui u
    int gradExt[5] = {0};      // d+(u) = cate arce pleaca din u
    int gradInt[5] = {0};      // d-(u) = cate arce intra in u

    for (int i = 0; i < m; i++) {
        int u = arce[i][0];
        int v = arce[i][1];
        adj[u].push_back(v);   // DOAR v in adj[u] (graf orientat)
        gradExt[u]++;          // din u mai pleaca un arc
        gradInt[v]++;          // in v mai intra un arc
        // ATENTIE: NU adaugam si u in adj[v] (asta ar fi graf neorientat)
    }

    for (int u = 1; u <= n; u++) {
        cout << u << ": ";
        for (int v : adj[u]) cout << v << " ";
        cout << " (d+ = " << gradExt[u] << ", d- = " << gradInt[u] << ")\n";
    }
    return 0;
}
// 1: 2 4  (d+ = 2, d- = 1)
// 2: 3  (d+ = 1, d- = 1)
// 3: 1  (d+ = 1, d- = 1)
// 4:  (d+ = 0, d- = 1)

Compară cu graful neorientat, unde aveai două push_back (adj[u].push_back(v) și adj[v].push_back(u)). Aici dispare a doua linie: un arc înseamnă un singur sens, deci o singură inserare — iar în locul unui singur vector de grade apar două, incrementate pe capete diferite ale arcului.

adj[u].push_back(v);
adj[v].push_back(u);   // GRESIT pentru graf orientat