Informatica, Grafuri 11C

Definiţie:
Se numeşte graf orientat sau disgraf G= (X, U), o pereche ordonată de mulţimi, unde X este o mulţime finită şi nevidă de elemente numite vârfuri sau noduri, iar U o mulţime de perechi ordonate de elemente din mulţimea X, numite arce.
Două vârfuri sunt adiacente dacă între ele există un arc. Fie arcul (X, Y) X se numeşte extremitate iniţială a arcului şi Y extremitate finală.
Se numesc două arce incidente dacă au o extremitate comună.
Se numesc succesorii unui nod X, toate vârfurile la care se poate ajunge cu un arc care iese din nodul X.
Se numeşte predecesor al nodului X, orice nod de la care porneşte un arc care intră.
Nod sursă al grafului este nodul care are mulţimea succesorilor formatş din toate celălalte noduri mai puţin el, iar mulţimea predecesorilor este mulţimea vidă.
Se numeşte nod terminal, nodul care are suma gradelor egală cu 1.
Se numeşte nod izolat, nodul care are suma gradelor egală cu 0.
Se numeşte grad intern al unui nod X şi se notează d⁻(X), numărul arcelor care intră din nodul X.
Se numeşte grad extern al unui nod X şi se notează d⁺(X), numărul arcelor care ies din nodul X.
Teoreme:
Numărul total de grafuri orientate care se pot forma cu n noduri este .
Pentru un graf orientat cu n noduri, suma gradelor interne a tuturor nodurilor este egală cu suma gradelor externe a tuturor nodurilor şi este egală cu numărul arcelor.