Graful orientat

Într-un graf orientat, legăturile sunt arce cu sens. Arcul $(1,2)$ permite deplasarea de la 1 la 2, dar nu implică și arcul $(2,1)$. Pentru arcele $(1,2)$ și $(2,3)$ există un drum orientat de la 1 la 3 prin 2, dar nu neapărat un drum invers.

Într-un graf orientat, legăturile sunt arce, adică perechi ordonate $(x,y)$: arcul pleacă din $x$ și intră în $y$. Arcul $(1,2)$ și arcul $(2,1)$ sunt arce distincte. Gradul extern al unui vârf este numărul arcelor care pleacă din el, iar gradul intern este numărul arcelor care intră în el. Pentru arcele $(1,2)$ și $(2,3)$, vârful 2 are gradul intern 1 și gradul extern 1, vârful 1 are gradul extern 1 și intern 0, iar vârful 3 are gradul intern 1 și extern 0.

Exemplul 1 — matricea de adiacență.

#include <iostream>
using namespace std;
int main() {
    int a[4][4] = {};
    a[1][2] = 1;
    a[2][3] = 1;
    cout << a[1][2] << " " << a[2][1];
}

Se afișează 1 0. Matricea de adiacență nu este neapărat simetrică: a[i][j] = 1 înseamnă că există arcul $(i,j)$. Suma liniei $i$ este gradul extern al lui $i$, iar suma coloanei $i$ este gradul intern. Suma gradelor interne și suma gradelor externe sunt fiecare egale cu numărul arcelor.

Exemplul 2 — gradele intern și extern. Graful are 4 vârfuri și arcele $(1,2)$, $(1,3)$, $(3,2)$, $(2,4)$, $(4,1)$. Programul calculează gradele din lista arcelor:

#include <iostream>
using namespace std;
int main() {
    int e[5][2] = {{1, 2}, {1, 3}, {3, 2}, {2, 4}, {4, 1}};
    int ext[5] = {}, in[5] = {};
    for (auto& r : e) { ++ext[r[0]]; ++in[r[1]]; }
    for (int i = 1; i <= 4; ++i)
        cout << i << ": " << ext[i] << " " << in[i] << "\n";
}

Se afișează 1: 2 1, 2: 1 2, 3: 1 1 și 4: 1 1, adică perechile (extern, intern). Suma gradelor externe este $2+1+1+1=5$, iar suma gradelor interne este $1+2+1+1=5$, deci ambele sunt egale cu numărul arcelor, nu cu dublul lui, cum se întâmplă la gradele din graful neorientat.

Exemplul 3 — matricea grafului din al doilea exemplu. Liniile matricei, pentru vârfurile 1, 2, 3, 4, sunt $(0,1,1,0)$, $(0,0,0,1)$, $(0,1,0,0)$ și $(1,0,0,0)$. Sumele liniilor sunt $2,1,1,1$, adică gradele externe, iar sumele coloanelor sunt $1,2,1,1$, adică gradele interne. Numărul valorilor 1 este 5, ca numărul arcelor. Dacă toate arcele își schimbă sensul, se obține matricea transpusă: liniile ei sunt $(0,0,0,1)$, $(1,0,1,0)$, $(1,0,0,0)$ și $(0,1,0,0)$, iar gradele interne și externe își schimbă rolurile. Un vârf cu ambele grade zero, adică o linie și o coloană formate numai din zerouri, este izolat.

Succesori și predecesori. Dacă $(x,y)$ este arc, $y$ este succesor al lui $x$, iar $x$ este predecesor al lui $y$. În graful din al doilea exemplu, succesorii lui 1 sunt 2 și 3, iar singurul lui predecesor este 4. Listele de succesori sunt 1: 2 3, 2: 4, 3: 2 și 4: 1; lungimea listei unui vârf este gradul lui extern. Ca și la graful neorientat, listele ocupă $O(n+m)$ spațiu, iar matricea $O(n^2)$, dar fiecare arc apare o singură dată în liste, nu de două ori.

Drum și circuit. Un drum respectă sensul arcelor. Un circuit orientat este un drum închis care respectă sensul arcelor. Pentru arcele $1\to 2$, $2\to 3$ și $3\to 1$, succesiunea $1\to 2\to 3\to 1$ este un circuit de lungime 3. Dacă ultimul arc lipsește, există doar drumul $1\to 2\to 3$, iar de la 3 nu se mai poate ajunge la 1. În graful din al doilea exemplu, $1\to 2\to 4\to 1$ este circuit, dar $2\to 1$ nu este arc, deci succesiunea $2\to 1$ nu este drum.

Într-un graf orientat simplu fără bucle, numărul maxim de arce este $n(n-1)$, deoarece ambele sensuri sunt posibile pentru fiecare pereche de vârfuri distincte. Pentru $n=3$, maximul este 6; pentru $n=4$, este 12. Numărul grafurilor orientate simple cu $n$ vârfuri fixate este $2^{n(n-1)}$, deoarece fiecare dintre cele $n(n-1)$ arce posibile există sau nu. La trasarea drumurilor, respectă sensul fiecărui arc. Numărul valorilor 1 din matrice este egal cu numărul arcelor, nu cu dublul lui, iar diagonala principală conține zerouri dacă nu există bucle. Un graf neorientat cu $m$ muchii poate fi privit ca un graf orientat cu $2m$ arce, câte unul în fiecare sens, motiv pentru care matricea lui este simetrică.

Exemplu în formatul examenului. Un graf orientat are vârfurile 1, 2, 3, 4 și arcele $(1,2)$, $(1,3)$, $(3,2)$, $(2,4)$, $(4,1)$. Pentru câte vârfuri gradul intern este egal cu gradul extern?

• a) 1
• b) 2
• c) 3
• d) 4

Răspunsul corect este b). Gradele (extern, intern) sunt: vârful 1 are $(2,1)$, vârful 2 are $(1,2)$, vârful 3 are $(1,1)$, iar vârful 4 are $(1,1)$. Egalitatea apare numai la vârfurile 3 și 4. Varianta d) ar rezulta din faptul că sumele gradelor sunt egale, dar egalitatea sumelor nu implică egalitatea vârf cu vârf. Varianta c) ia în calcul și un vârf, 1 sau 2, la care cele două grade diferă. Varianta a) numără un singur vârf dintre cele două.

Greșeli frecvente

• Greșit: arcul $(1,2)$ implică arcul $(2,1)$.
  Corect: acestea sunt arce distincte.
• Greșit: matricea de adiacență trebuie să fie simetrică.
  Corect: într-un graf orientat nu este obligatoriu.
• Greșit: suma gradelor exterioare este dublul numărului de arce.
  Corect: este egală cu numărul arcelor.

Înainte și după