Grafuri orientate

Pentru reprezentarea grafică a unui graf orientat, avem în vedere următoarele:

• nodurile sunt reprezentate de cercuri numerotate;
• arcele se reprezintă prin segmente orientate (cu sens).

Ordinea extremităților arcelor contează. Muchiile sunt de la primul la al doilea nod.

Când ne referim la grafurile orientate, este bine să cunoaștem următorii termeni și definiții:

Nod (vârf)

Nodurile sunt punctele grafului orientat, alcătuind mulțimea nodurilor.

Ele sunt etichetate în general fie cu cifre, fie cu litere, pentru a putea fi diferențiate. Mulțimea de noduri se notează cu $X$ și conține toate nodurile grafului.

Exemplu:

• pentru graful descris mai sus, mulțimea nodurilor este $X={1,2,3,4,5,6}$.

Arce

Arcele sunt legături ordonate între nodurile grafului.

Extremitățile unui arc se scriu între paranteze rotunde, ordinea acestora fiind importantă în determinarea sensului arcului.

Fie $(x, y)$ un arc:

• $x$ se numește extremitate inițială a arcului;
• $y$ se numește extremitate finală a arcului.

Adiacență

Două noduri $x$ și $y$ se numesc adiacente dacă formează un arc.

Exemplu:

• În graful de mai sus, nodul $2$ este adiacent cu nodurile $1$, $3$ și $4$.

Incidență

Două arce se numesc incidente dacă au o extremitate comună.

Exemple (graful anterior):

• arcul $(6,3)$ este incident cu arcul $(3,4) <=> 3$ este vârf comun;
• arcul $(1,2)$ nu este incident cu arcul $(5,6)$, deoarece nu au niciun nod în comun.

Un nod este incident cu un arc dacă este extremitate al acestuia.

Exemple (graful anterior):

• nodul $3$ este incident cu arcul $(1,3)$ și arcul $(6,3)$;
• nodul $1$ nu este incident cu arcul $(3,4)$, deoarece nu este extremitate al acestuia.

Gradul nodurilor

Gradul unui nod $x$ reprezintă numărul de noduri adiacente cu $x$ (sau numărul de arce incidente cu $x$).

La grafuri orientate, avem două tipuri de grade:

• Gradul interior reprezintă numărul arcelor care au extremitatea finală în nod și este notat cu $d^{-}(x)$;
• Gradul exterior reprezintă numărul arcelor care au extremitatea inițială în nod și este notat cu $d^{+}(x)$.

Exemple (graful anterior):

• $d^{-}(1)=1$ ; $d^{+}(1)=2$
• $d^{-}(3)=3$ ; $d^{+}(3)=1$
• $d^{-}(6)=1$ ; $d^{+}(6)=1$

Un nod izolat în graful orientat are ambele grade egale cu $0$.

Grafurile orientate au anumite proprietăți, din care se pot genera mai multe formule utile:

• numărul maxim de arce într-un graf orientat cu $n$ noduri este $A^{2}_{n}$, sau $n*(n-1)$;
• suma gradelor nodurilor unui graf orientat este egală cu dublul numărului de arce, deci $2*m$;
• numărul de grafuri orientate ce se pot forma cu n vârfuri este egal cu $2^{A^{2}_{n}}$, sau $2^{n*(n-1)}$.