Definiția 1 : Un graf orientat este o pereche ordonată de mulțimi G = (V, U) , unde: -Veste mulțimea vârfurilor (nodurilor ), mulțime finită și… [621110]

GRAFURI ORIENTATE –INTRODUCERE
Definiția 1 : Un graf orientat este o pereche ordonată de mulțimi
G = (V, U) , unde:
-Veste mulțimea vârfurilor (nodurilor ), mulțime finită și nevidă ;
-Ueste mulțimea arcelor , o mulțime de perechi ordonate din
mulțimea V.
Exemplu de graf orientat:1
56
32
4Teorema 1 :
Numărul degrafuri orientate
cunvârfuri care sepot obți-
neeste :
2)1n(n
4

GRAFURI ORIENTATE –INTRODUCERE
Adiacență și incidență
Nodurile distincte x,yVsunt
adiacente dacă există cel
puțin unarccare leunește .
Dacă există arcul (x,y),acesta este
incident spre exterior cuxși
incident spre interior cuy.
Dacă există arcul (y,x),acesta este
incident spre interior cuxși
incident spre exterior cuy.
V = {1, 2, 3, 4, 5, 6}
U = { (1, 2) , (1, 5), (1, 6), (2, 1) , (2, 3), (3, 1), (3, 6), (4, 3),
(5, 2), (5, 4), (6, 5)}1
56
32
4

GRAFURI ORIENTATE –INTRODUCERE
Gradul unui vârf
Definiția 2:Gradul exterior alunui vârf x,
notat d+(x),reprezintă numărul arcelor
incidente spre exterior cux.
Definiția 3:Gradul interior alunui vârf x,
notat d-(x),reprezintă numărul arcelor
incidente spre interior cux.
Definiția 4:Gradul unui vârf xreprezintă
suma dintre gradele exterior șiinterior ale
luix.
d(x)=d+(x)+d-(x)
Observații :
1.Un vârf care nu este adiacent cu nici un
alt vârf se numește vârf izolat .
2.Un vârf care este adiacent doar cu un
alt vârf se numește vârf terminal .d+(1) = 1, d-(1) = 2, d(1) = 3
6 este vârf izolat.
5este vârf terminal.1
56
32
4

GRAFURI ORIENTATE –DRUMURI
Definiția 5:Senumește drum îngraful
orientat G,osuccesiune devârfuri D=(x1,
x2,…,xk),unde (x1,x2)U,(x2,x3)U,…,
(xk-1,xk)U.
Observații :
3. Vârfurile x1și xkse numesc extremitățile
drumului .
4. Numărul de arce ale drumului reprezintă
lungimea sa.
5.Dacă vârfurile x1,x2,…,xksunt distincte
două câte două, drumul senumește
elementar .Încaz contrar, drumul se
numește ne-elementar .D1=(1,2,3,6,5)
D1este elementar .
D2=(2,3,6,5,4,3,1)
D2este ne-elementar .
D3=(5,2,3,6,5,4,3)
D3este ne-elementar .1
56
32
4

GRAFURI ORIENTATE –CIRCUITE
Definiția 6:Senumește circuit îngraful
orientat G,undrum C=(x1,x2,…,xk),unde
x1,x2,…,xkV,cuproprietatea că
x1=xkșiarcele (x1,x2),(x2,x3),…,(xk-1,xk)
sunt distincte două câte două .
Observații :
6. Vârfurile x1și xkse numesc extremitățile
circuitului .
7. Numărul de arce ale circuitului reprezin –
tă lungimea sa.
8.Dacă toate vârfurile circuitului, cu
excepția extremităților, sunt distincte
două câte două, circuitul senumește
elementar .Încaz contrar, circuitul se
numește neelementar .C1=(1,2,3,1)
C1este elementar .
C2=(2,3,6,5,4,3,1,2)
C2este ne-elementar .
C3=(5,4,3,6,5,2,1,5)
C3este ne-elementar .1
532
46

GRAFURI ORIENTATE –SUBGRAFURI
Definiția 7:Senumește subgraf alunui
graf orientat G=(V,U),ungraf G1=(V1,
U1),unde V1VșiU1U,cu
proprietatea căU1va conține doar
arcele incidente cuvârfuri dinmulțimea
V1.
Observația 9:
Unsubgraf G1sepoate obține dingraful
orientat Geliminând unul saumai multe
vârfuri șiarcele incidente cuacestea .G
G1
Am eliminat vârfurile 1 și 4, precum și
arcele corespunzătoare.1
532
46
5326

GRAFURI ORIENTATE –GRAFURI PARȚIALE
Definiția 8:Senumește graf parțial al
unui graf orientat G=(V,U),ungraf G1=
(V,U1),unde U1U.
Observația 10:
Ungraf parțial G1sepoate obține din
graful orientat Geliminând unul saumai
multe arce .
Am eliminat arcele (1, 2), (2, 1), (3, 1) și (1,5).G1
532
46
1
532
46G1

GRAFURI ORIENTATE –GRAFURI COMPLETE
Definiția 9:Senumește graf complet un graf
orientat încare oricare două vârfuri distincte sunt
adiacente .
) (nn m) (nn121

   n
in
ii i m xd xd
1 1)( )(
Teorema 2:
Într-ungraf orientat G=(V,U)cunvârfuri șim
arce, suma gradelor exterioare ale tuturor
vârfurilor este egală cusuma gradelor interioare
aletuturor vârfurilor șieste egală cunumărul de
arce .
Teorema 3:
Numărul mde arce pentru un graf complet
satisface relația :1
532
46
Teorema 4:
Numărul de grafuri orientate complete cun
vârfuri este :
2)1(
3nn

GRAFURI ORIENTATE –GRAFURI TARE CONEXE
Definiția 10:Senumește graf tare conex ungraf
orientat cuproprietatea căpentru oricare două
vârfuri x,yV,există drum delaxlayșidrum
delaylax.
Definiția 11:
Senumește componentă tare conexă aunui
graf orientat G=(V, U),un subgraf
G1=(V1,U1)alluiG,tare conex, cuproprietatea
căoricare arfixV-V1,subgraful luiG
determinat deV1U{x}numai este tare conex .
Observația 11:
Ungraf tare conex are osingură componentă
tare conexă .
Graful din stânga are 4componente tare
conexe .1
532
4671
532
467

GRAFURI ORIENTATE –METODE DE REPREZENTARE
Matricea deadiacență
Este omatrice Acunlinii șincoloane,
unde :
 altfel 0,ji U,j) (i, dacă 1,)j,i(a
Pentru graful alăturat avem următoarea
matrice deadiacență :





0000000100100000010000010000000101000000010000100
A1
532
467

GRAFURI ORIENTATE –METODE DE REPREZENTARE
Matricea deadiacență
Matricea de adiacență a unui graf orientat are următoarele proprietăți:
-este pătratică ;
-este binară ;
-nu este simetrică față de diagonala principală;
-diagonala principală conține doar valori egale cu 0 ;
-suma elementelor de pe linia ireprezintă gradul exterior al vârfului i;
-suma elementelor de pe coloana ireprezintă gradul interior al vârfului i;
-suma tuturor elementelor reprezintă numărul mal arcelor.1
532
467





0000000100100000010000010000000101000000010000100
A

GRAFURI ORIENTATE –METODE DE REPREZENTARE
Liste deadiacență
Sememorează, pentru fiecare vârf, lista
vârfurilor adiacente cuel.
Pentru graful alăturat avem următoarele
liste deadiacență :
Vârful Lista vârfurilor adiacente
1
2
3
4
5
63
1
2, 4
5
4
4, 71
532
467
7 –

GRAFURI ORIENTATE –METODE DE REPREZENTARE
Vectorul arcelor
Fiecare arcalgrafului sememorează sub
forma unei înregistrări (record ,structură ).
Pentru graful alăturat avem următorul
vector alarcelor :
//tipdedate definit deutilizator
struct arc
{intx,y;
};
//singurul cazînC++ când sepune ;după }
arcv[100];
//vector cuelemente detiparc1
532
467