# Grafuri orientate

> Pagina: https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori/graf-orientat
> Markdown: https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori/graf-orientat.md
> Sursa: Bacalaurescu (bacalaurescu.ro), conținut gratuit pentru BAC 2027.

Materia: [Informatică](https://bacalaurescu.ro/informatica)

Capitolul: [Grafuri orientate și arbori](https://bacalaurescu.ro/informatica/lectii/grafuri-orientate-si-arbori)
Actualizat: 2026-09-22

Arc, grad intern și extern, drum, circuit și tare conexitate.

## 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.

> [!RETINE]
> La graf orientat **nu se împarte la 2**, pentru că matricea nu mai e simetrică. E cea mai frecventă greșeală la trecerea de la neorientat la orientat.

## 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).