Grafuri Orientate

Un graf orientat G este format dintr-o pereche ordonata de multimi G=(X,U). ca si in cazul grafurilor neorientate, X este multimea varfurilor sau nodurilor grafului.Multimea U este formata din perechi ordonate de elemente distincte din X, numite arce.Orice arc uÎ U va fi notat prin u=(x,y) cu x,yÎX si x¹y.

Spunem ca varful x este extremitatea initiala a arcului u, iar varful y este extremitatea finala a arcului u. Spre deosebire de cazul grafurilor neorientate, notatiile(x,y) si (y,x) vor desemna doua arce diferite.

Daca graful G contine arcul (x,y) vom spune ca varfurile x si y sunt adiacente in G si amandoua sunt incidente cu arcul (x,y). Deci, un graf orientat G poate fi imaginat ca o multime de varfuri, dintre care unele sunt unite doua cate doua prin arce. Un graf orientat poate fi desenat in plan reprezentand varfurile sale prin puncte si arcele prin sageti care sunt orientate de la extremitatea initiala catre extremitatea finala a fiecarui arc.

Graful orientat G=(X,U) unde:

X={ 1,2, …. ,8} si U={(1,2), (2,3), (3,1), (3,2), (2,4), (4,5), (3,5), (6,8), (8,7), (7,8),(7,6)} se reprezinta ca in figura:

Vom nota arcele asa cum se indica in figura , adica u1=(1,2), u2=(3,1),…., u11=(6,8).

Gradul exterior al unui varf x, notat prin d¬+(x), este numarul arcelor de forma (x,y) cu yÎX. Gradul exterior al unui varf x, notat prin d-(x),este numarul arcelor de forma (y,x) cu yÎX.

Un graf partial al unui graf orientat G=(X,U) se defineste in acelasi mod ca si in cazul neorientat. El este un graf G1=(X,V) unde VÌU, deci este graful G insusi sau se obtine din G prin suprimarea anumitor arce.

Si definitia unui subgraf al unui graf orientat G=(X,U) este asemanatoare cu cazul neorientat.Prin definitie , un subgraf al lui G este un graf H=(Y,V), unde YÌX, iar arcele din V sunt toate arcele din U care au ambele extremitati in multimea de varfuri Y.

Deci un subgraf H al unui graf orientat G este graful G insusi sau se obtine din G prin suprimarea anumitor varfuri si a tuturor arcelor incidente cu acestea .

Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y.

Astfel,subgraful grafului G din figura ,indus de multimea de varfuri Y¬1 ={1,2,4,5} are ca multime de arce multimea V1 ={(1,2), (2,4), (4,5)},iar subgraful indus de multimea de varfuri Y2 ={6,7,8} are multimea arcelor V2={(7,6),(6,8),(7,8),(8,7)}.

Un graf orientat este complet daca oricare doua varfuri sunt adiacente.

In timp ce in cazul neorientat un graf complet cu n varfuri este unic determinat, in cazul orientat exista mai multe grafuri complete cu un numar dat de varfuri.Ele se deosebesc fie prin orientarea arcelor , fie prin faptul ca intre doua varfuri oarecare exista un arc sau doua arce de sensuri contrare.

Un lant al unui graf orientat se defineste ca un sir de arce:

L=[u1,u2,…..,up]

Cu proprietatea ca oricare arc uI din acest sir are comuna o extremitate cu ui-1 , iar cealalta extremitate este comuna cu ui+1 pentru orice i=1,...,p-1.

Daca toate arcele lantului L au aceeasi orientare ,care este data de sensul deplasarii de la x0 catre xr lantul se numeste drum.

Deci un drum intr-un graf orientat G=(X,U) este un sir de varfuri notat :