Definiţii
Se numeşte graf orientat sau digraf o pereche de mulţimi (X, U), unde X este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U este o mulţime de perechi ordonate formate cu elemente distincte din mulţimea X, numite arce.
Mulţimea arcelor care ies dintr-un nod: ω +
Mulţimea arcelor care intră într-un nod: ω-
În graful G=(X,U) avem:
X = 1, 2, 3, 4, 5.
U={ (5,3), (1, 2), (1, 3), (1,4), (1,5), (2,3), (2,4), (2, 5), (3,4), (4, 5)}
Numim vârfuri adiacente orice pereche de vârfuri care formează un arc. Două vârfuri spunem că sunt incidente cu arcul pe care îl formează.
Pentru arcul (x, y) spunem că x este extremitatea iniţială şi y este extremitatea finală.
Spunem că doua arce sunt incidente dacă au o extremitate comună.
Se numeşte succesor al vârfului x orice vârf la care ajunge un arc care iese din x.
Mulţimea succesorilor se notează: Γ+.
Se numeşte predecesor al vârfului x orice vârf de la care intră un arc în vârful x.
Mulţimea predecesorilor se notează: Γ-.
Gradul intern al unui nod este egal cu numărul arcelor care intră în nod şi se notează d-(x).
Gradul extern al unui nod este egal cu numărul arcelor care ies din nod şi se notează d+(x).
Teoreme
Teorema 1: Numărul total de grafuri orientate cu n noduri este n(n-1)/2;
Teorema 2: Într-un graf orientat cu n noduri suma gradelor interne este egală cu suma gradelor externe şi este egală cu numărul arcelor.
Aplicaţii ale definiţiilor
Mulţimea arcelor care intră în nodul 2: ω +(2)= {(2, 5), (2, 3), (2, 4)};
Mulţimea arcelor care ies din nodul 2: ω- (2)={(1, 2)};
Nodurile 2 si 4 sunt adiacente.
Pentru arcul (2, 3) spunem ca 2 este extremitatea iniţială şi 3 este extremitatea finală.
Arcele (2, 3) şi (3, 4) sunt incidente.
Nodul 4 este succesor al nodului 2.
Nodul 2 este predecesor al nodului 4.
Mulţimea succesorilor nodului 2: Γ+2= {3, 4, 5};
Mulţimea predecesorilor nodului 2: Γ-2={1};
Gradul extern al nodului 2: 3
Grad intern al nodului 2: 1