Grafuri orientate teorie
Se numeste graf orientat o pereche ordonata de multimi G=(x,u) unde x este o multime infinita si nevida numita multimea varfurilor,iar u este formata din perechi ordonate de elemente distincte,din x se numeste multimea arcelor.
Daca intr-un graf orientat exista arcul u=(x,y) se spune ca varfurile x,y sunt adiacente intre ele si incidente cu arcul u.
Se numeste grad exterior al unui varf x si se noteaza d+(x) numar arcelor care ies din varful x.
Se numeste grad interior al unui varf x si se noteaza d-(x) nr arcelor care intra in x.
Se noteaza Γ+(x)={y|(x,y)∈u},multimea succesorilor varfului x.
Se noteaza Γ-(x)={y|(y,x)∈u},multimea predecesorilor varfului x.
Se noteaza ω+(x)={u|u=(x,y)∈u},multimea arcelor care ies din varful x.
Se noteaza ω-(x)={u|u=(y,x)∈u},multimea arcelor care intra in varful x.
Se numeste varf izolat un varf care are atat gradul interior cat si cel exterior egal cu 0.
Se numeste varf terminal un varf care are gradul interior 1 si exterior 0.
Se numeste lant intr-un graf orientat o succesiune de arce cu proprietatea ca 2 arce vecine au o extremitate comnuna.
Se numeste drum un lant in care arcele au aceeasi orientare.
Se numeste drum elementar un varf in care varfurile sunt distincte 2 cate 2.
Se numeste circuit un drum in care toate arcele sunt distincte si extremitatea initiala coincide cu cea finala.
Se numeste circuit elementar un circuit in care extremitatea initiala coincide cu cea finala si celelalte varfuri sunt distincte 2 cate 2.
Se numeste graf partial al unui graf orientat Gr =(x,u) si se noteaza cu H=(x,u) cu v<=u, un graf care se obtine din cel initial prin eliminarea unor arce.
Se numeste subgraf al unui graf orientat Gr=(x,u) si se noateaza cu H=(y,u) cu y<=x, un graf care se obtine din graful initial prin eliminarea unor varfuri si a arcelor incidente cu acestea.
Se numeste graf conex un graf orientat in care pentru orice pereche (x,y) exista un lant.
Se numeste graf tare conex un graf orientat in care pentru orice pereche de varfuri x,y exista drum de la x la y si de la y la x.
Se numeste componenta tare conexa a unui graf orientat un sub graf tare conex care este maximal in raport cu aceasta proprietate,adica pentru orice varf eliminat din graful initial,graful care se obtine din el impreuna cu subgraful nu mai este tare conex.
Se numeste drum hamiltonian intr-un graf orientat,un punct care contine toate varfurile grafului.
Se numeste circuit hamiltonian un crcuit elementar care contine toate varfurile grafului.
Se numeste graf hamiltonian un graf care contine un circuit hamiltonian.
Se numeste drum eulerian un drum care contine toate arcele grafului.
Se numeste circuit eulerian un circuit care contine toate arcele grafului.
Se numeste graf eulerian un graf care contine un circuit eulerian.
Se numeste grad exterior al unui varf x si se noteaza d+(x) numar arcelor care ies din varful x.
Se numeste grad interior al unui varf x si se noteaza d-(x) nr arcelor care intra in x.
Se noteaza Γ+(x)={y|(x,y)∈u},multimea succesorilor varfului x.
Se noteaza Γ-(x)={y|(y,x)∈u},multimea predecesorilor varfului x.
Se noteaza ω+(x)={u|u=(x,y)∈u},multimea arcelor care ies din varful x.
Se noteaza ω-(x)={u|u=(y,x)∈u},multimea arcelor care intra in varful x.
Se numeste varf izolat un varf care are atat gradul interior cat si cel exterior egal cu 0.
Se numeste varf terminal un varf care are gradul interior 1 si exterior 0.
Se numeste lant intr-un graf orientat o succesiune de arce cu proprietatea ca 2 arce vecine au o extremitate comnuna.
Se numeste drum un lant in care arcele au aceeasi orientare.
Se numeste drum elementar un varf in care varfurile sunt distincte 2 cate 2.
Se numeste circuit un drum in care toate arcele sunt distincte si extremitatea initiala coincide cu cea finala.
Se numeste circuit elementar un circuit in care extremitatea initiala coincide cu cea finala si celelalte varfuri sunt distincte 2 cate 2.
Se numeste graf partial al unui graf orientat Gr =(x,u) si se noteaza cu H=(x,u) cu v<=u, un graf care se obtine din cel initial prin eliminarea unor arce.
Se numeste subgraf al unui graf orientat Gr=(x,u) si se noateaza cu H=(y,u) cu y<=x, un graf care se obtine din graful initial prin eliminarea unor varfuri si a arcelor incidente cu acestea.
Se numeste graf conex un graf orientat in care pentru orice pereche (x,y) exista un lant.
Se numeste graf tare conex un graf orientat in care pentru orice pereche de varfuri x,y exista drum de la x la y si de la y la x.
Se numeste componenta tare conexa a unui graf orientat un sub graf tare conex care este maximal in raport cu aceasta proprietate,adica pentru orice varf eliminat din graful initial,graful care se obtine din el impreuna cu subgraful nu mai este tare conex.
Se numeste drum hamiltonian intr-un graf orientat,un punct care contine toate varfurile grafului.
Se numeste circuit hamiltonian un crcuit elementar care contine toate varfurile grafului.
Se numeste graf hamiltonian un graf care contine un circuit hamiltonian.
Se numeste drum eulerian un drum care contine toate arcele grafului.
Se numeste circuit eulerian un circuit care contine toate arcele grafului.
Se numeste graf eulerian un graf care contine un circuit eulerian.