Grafuri orientate

Ce se schimbă față de graful neorientat

Într-un graf orientat, legătura dintre noduri are sens. Se numește arc și se notează $(x, y)$, cu $x$ extremitate inițială și $y$ extremitate finală.

$(x, y)$ și $(y, x)$ sunt arce diferite.

Terminologie

• Grad extern $d^+(x)$: numărul de arce care pleacă din $x$.
• Grad intern $d^-(x)$: numărul de arce care intră în $x$.
• Drum: succesiune de noduri în care fiecare arc respectă sensul.
• Drum elementar: drum fără noduri repetate.
• Circuit: drum în care primul nod coincide cu ultimul.
• Circuit elementar: circuit fără noduri repetate, în afară de primul și ultimul.
• Lungime: numărul de arce.
• Subgraf și graf parțial: la fel ca la neorientat (scoți noduri, respectiv doar arce).

Teorema gradelor

$\sum_{x \in V} d^+(x) = \sum_{x \in V} d^-(x) = m$

Suma gradelor externe egalează suma gradelor interne și amândouă dau numărul de arce. Fiecare arc pleacă exact dintr-un nod și intră exact în altul.

Tare conexitate

Un graf orientat e tare conex dacă între oricare două noduri $x$ și $y$ există drum de la $x$ la $y$ și drum de la $y$ la $x$.

O componentă tare conexă e un subgraf tare conex maximal.

Matricea de adiacență

$a[i][j] = 1 \text{ dacă există arcul } (i, j)$

Nu mai e simetrică. De aceea:

• gradul extern al nodului $i$ = suma de pe linia $i$;
• gradul intern al nodului $i$ = suma de pe coloana $i$;
• numărul de arce = suma tuturor elementelor, fără să se împartă la 2.

Greșeli frecvente

1. Se împarte la 2 numărul de arce.
2. Se confundă gradul intern cu cel extern. Linie = extern (pleacă), coloană = intern (intră).
3. Se confundă conexitatea (pe graf neorientat) cu tare conexitatea (pe orientat).

#include <iostream>
using namespace std;

int main() {
    int n, m, a[101][101] = {0};
    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        int ext = 0, intern = 0;
        for (int j = 1; j <= n; j++) {
            ext += a[i][j];
            intern += a[j][i];
        }
        cout << i << ": d+=" << ext << " d-=" << intern << "\n";
    }
    return 0;
}