Grafuri orientate

Ce se schimbă când muchiile au sens: grade interioare și exterioare, drumuri, și de ce matricea nu mai este simetrică.

Diferența

Într-un graf orientat, legăturile au sens. Se numesc arce, se notează (x, y) și înseamnă „de la x spre y".

(x, y) și (y, x) sunt acum două arce diferite. Pot exista amândouă, unul singur, sau niciunul.

Cu ele modelezi relații asimetrice: străzi cu sens unic, dependențe între activități, „cine urmărește pe cine".

Unde stă față de programă. Programa de bacalaureat din 2022 conține doar grafurile neorientate și arborii. Grafurile orientate au ieșit din ea. Subiectele din 2019–2021, pe care le găsești pe platformă, au fost date după programa de atunci și încă le conțin. De aceea lecția rămâne aici, în formă scurtă. Dacă dai examenul după programa actuală, citește-o ca să înțelegi acele subiecte, nu pentru că ți se va cere.

Reprezentarea

Matricea de adiacență se construiește la fel, dar cu o singură atribuire:

cin >> x >> y;
a[x][y] = 1;        // atât — fără a[y][x]

Aceasta este singura modificare de cod față de grafurile neorientate. Tot aici se greșește în ambele sensuri: a[y][x] uitat la neorientate, a[y][x] pus în plus la orientate.

Matricea nu mai este simetrică. Dacă totuși este simetrică, graful este de fapt neorientat.

Două grade în loc de unul

Gradul exterior al lui x: câte arce pleacă din x, adică suma liniei x.

Gradul interior al lui x: câte arce intră în x, adică suma coloanei x.

int ext = 0, intr = 0;
for (int i = 1; i <= n; i++) {
    ext += a[x][i];      // linia
    intr += a[i][x];     // coloana
}

Suma tuturor gradelor exterioare este egală cu suma tuturor gradelor interioare. Amândouă sunt egale cu numărul de arce m, nu cu 2m ca la grafurile neorientate. Fiecare arc contribuie o dată la fiecare sumă.

Câteva cazuri speciale:

• Grad interior 0: nimic nu intră. Punct de plecare.
• Grad exterior 0: nimic nu iese. Punct de sosire.
• Ambele 0: vârf izolat.

Drumuri și circuite

Drum: succesiune de vârfuri în care fiecare pereche consecutivă este un arc, în sensul potrivit. Este corespondentul lanțului.

Circuit: drum care se întoarce în punctul de plecare. Este corespondentul ciclului.

Spre deosebire de grafurile neorientate, un drum de la x la y nu garantează unul de la y la x. Aproape toate greșelile de la acest capitol vin de aici.

Un graf orientat poate avea un circuit de lungime 2: arcele (x, y) și (y, x) la un loc. La grafuri neorientate, cel mai scurt ciclu are lungimea 3.

Parcurgerile

Codul este identic cu cel de la grafuri neorientate. Matricea are deja sensurile în ea, iar a[x][y] == 1 înseamnă acum „pot merge de la x la y".

void df(int x) {
    vizitat[x] = true;
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && !vizitat[y])
            df(y);
}

Se schimbă doar interpretarea: pornind din x, parcurgerea găsește vârfurile accesibile din x, nu pe cele „legate de" x.

Ca să afli din ce vârfuri se poate ajunge în x, parcurgi pe coloane în loc de linii, adică pe graful cu toate arcele inversate:

if (a[y][x] == 1 && !vizitat[y])

Conexitatea, care se complică

La grafuri orientate există două noțiuni:

Tare conex: între oricare două vârfuri există drum în ambele sensuri.

Slab conex: graful devine conex dacă ignori sensurile.

Un graf poate fi slab conex fără să fie tare conex. Un exemplu sunt două vârfuri legate printr-un singur arc.

O verificare simplă pentru tare conexitate, când n este mic: pentru fiecare vârf, pornești o parcurgere și verifici că ajunge la toate celelalte. Costă n parcurgeri, lucru perfect acceptabil la dimensiunile de la bac.

Un exemplu complet

Se citește un graf orientat. Să se afișeze vârfurile din care nu pleacă niciun arc și vârfurile în care nu intră niciun arc.

#include <iostream>
using namespace std;

int a[101][101], n, m;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }

    cout << "fara arce care pleaca: ";
    for (int i = 1; i <= n; i++) {
        int ext = 0;
        for (int j = 1; j <= n; j++) ext += a[i][j];
        if (ext == 0) cout << i << " ";
    }

    cout << "\nfara arce care intra: ";
    for (int i = 1; i <= n; i++) {
        int intr = 0;
        for (int j = 1; j <= n; j++) intr += a[j][i];
        if (intr == 0) cout << i << " ";
    }

    return 0;
}

Cele două bucle interioare diferă doar prin ordinea indicilor: a[i][j] pentru linie, a[j][i] pentru coloană. Verifică-le de două ori, pentru că aici se greșește.

De reținut

• La orientate, a[x][y] = 1 fără a[y][x]. Matricea nu mai e simetrică.
• Grad exterior = suma liniei. Grad interior = suma coloanei.
• Suma gradelor exterioare = suma celor interioare = m (nu 2m).
• Drum de la x la y nu înseamnă drum de la y la x.
• Codul parcurgerilor este neschimbat. Se schimbă doar interpretarea.
• Tare conex = drum în ambele sensuri. Slab conex = conex ignorând sensurile.