Grafuri orientate: arce, grad intern și extern, drumuri

Grafurile orientate seamănă cu cele neorientate, dar au o diferență esențială: legăturile au sens. Dacă te gândești la o rețea de străzi, un graf neorientat are doar străzi cu dublu sens, iar unul orientat poate avea și străzi cu sens unic. La BAC Informatică, itemii despre grafuri orientate verifică exact consecințele acestei diferențe: gradul intern și extern, matricea de adiacență nesimetrică și drumurile care trebuie să respecte sensul arcelor.

Arce în loc de muchii

Un graf orientat este o pereche G = (V, A), unde V este mulțimea nodurilor, iar A este mulțimea arcelor. Un arc este o pereche ordonată (x, y): pleacă din x și ajunge în y. Spre deosebire de muchiile [x, y], arcele (x, y) și (y, x) sunt diferite și pot exista amândouă în același graf.

Pentru arcul (x, y), nodul x se numește extremitate inițială, iar y extremitate finală. Spunem că y este succesor al lui x, iar x este predecesor al lui y.

Exemplul cu care lucrăm

Fie graful orientat cu n = 4 noduri și m = 5 arce: (1,2), (2,3), (3,1), (3,4), (4,2).

Matricea de adiacență are a[i][j] = 1 dacă există arcul (i, j):

     1  2  3  4
 1   0  1  0  0
 2   0  0  1  0
 3   1  0  0  1
 4   0  1  0  0

Observă că matricea nu mai este simetrică: a[1][2] = 1, dar a[2][1] = 0, pentru că arcul (1,2) există, iar (2,1) nu. Diagonala principală rămâne plină de 0.

Gradul intern și gradul extern

Fiecare nod are acum două grade:

• gradul extern d⁺(x) = numărul de arce care pleacă din x = suma elementelor de pe linia x;
• gradul intern d⁻(x) = numărul de arce care intră în x = suma elementelor de pe coloana x.

Suma gradelor externe este 1 + 1 + 2 + 1 = 5, iar suma gradelor interne este 1 + 2 + 1 + 1 = 5. Ambele sunt egale cu numărul de arce, pentru că fiecare arc pleacă dintr-un singur nod și intră într-un singur nod:

Σ d⁺(x) = Σ d⁻(x) = m.

Compară cu graful neorientat, unde suma gradelor era 2m. Această diferență apare des în grile ca variantă-capcană.

Numărul maxim de arce și numărul de grafuri

Într-un graf orientat fără bucle, din fiecare nod pot pleca arce către celelalte n − 1 noduri, deci numărul maxim de arce este n(n−1), dublu față de cazul neorientat. Pentru n = 4, cel mult 12 arce.

Pentru numărul de grafuri orientate cu n noduri date, gândește pe perechi de noduri {x, y}. Fiecare pereche are 4 variante: niciun arc, doar (x, y), doar (y, x) sau ambele arce. Cum există n(n−1)/2 perechi, numărul total de grafuri orientate este 4 la puterea n(n−1)/2. Pentru n = 3: 4³ = 64.

Drumuri și circuite

În graful neorientat vorbim despre lanțuri; în graful orientat, echivalentul care respectă sensul arcelor este drumul: o succesiune de noduri x₁, x₂, …, xₖ în care fiecare pereche consecutivă (xᵢ, xᵢ₊₁) este un arc. Lungimea drumului este numărul de arce.

• Un drum este elementar dacă nodurile lui sunt distincte.
• Un circuit este un drum în care primul nod coincide cu ultimul și arcele sunt distincte.

În exemplul nostru:

• 1 → 2 → 3 → 4 este un drum elementar de lungime 3 de la 1 la 4.
• 1 → 2 → 3 → 1 și 2 → 3 → 4 → 2 sunt circuite de lungime 3.
• 2 → 1 nu este un drum, pentru că arcul (2,1) nu există, chiar dacă (1,2) există.

Dacă ignori sensul arcelor, obții graful neorientat asociat; un lanț în acesta nu e neapărat drum în graful orientat. Multe grile testează exact această diferență.

Graf tare conex

Un graf orientat este tare conex dacă pentru oricare două noduri x și y există un drum de la x la y și un drum de la y la x. Graful nostru este tare conex: din 1 ajungi oriunde pe drumul 1 → 2 → 3 → 4, iar din 4 te întorci pe 4 → 2 → 3 → 1. Dacă ai elimina arcul (4,2), din nodul 4 n-ar mai pleca niciun arc, deci graful n-ar mai fi tare conex.

Un indiciu rapid: dacă un nod are d⁺ = 0 (nu pleacă nimic din el) sau d⁻ = 0 (nu intră nimic în el) și graful are cel puțin două noduri, graful sigur nu este tare conex.

Calculul gradelor în C++

Când ai nevoie doar de grade, nu trebuie neapărat să construiești matricea: e suficient să numeri, pentru fiecare arc citit, o ieșire pentru x și o intrare pentru y. Programul de mai jos afișează nodurile care au gradul intern egal cu gradul extern:

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

int dplus[101], dminus[101];

int main()
{
    ifstream fin("graf.in");
    int n, m, x, y;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y;      // arcul (x, y)
        dplus[x]++;        // un arc pleacă din x
        dminus[y]++;       // un arc intră în y
    }
    for (int i = 1; i <= n; i++)
        if (dplus[i] == dminus[i])
            cout << i << ' ';
    fin.close();
    return 0;
}

Pentru exemplul nostru, programul afișează 1 4: nodurile 1 și 4 au câte un arc care intră și unul care pleacă, în timp ce nodul 2 are d⁻ = 2, d⁺ = 1, iar nodul 3 are d⁺ = 2, d⁻ = 1.

Neorientat vs. orientat, pe scurt