Grafuri Orientate.Definitii.Teoreme.Aplicatii

         

             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 ordonateformate 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).
TeoremeTeorema 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