Grafuri orientate [604918]

Grafuri orientate

Definiție :
Senumește graf orientat opereche ordonată demulțimi (X,U),unde :
–Xesteomulțime finită șinevidă deelemente, numite noduri sauvârfuri ;
–Uesteomulțime deperechi ordonate dinX,numite arce.
Xsenumește mulțimea nodurilor sauvârfurilor
Usenumește mulțimea arcelor .

Definiție :
Pentru unarcu=[x,y]:
–xsenumește extremitatea inițială ,iarysenumește extremitatea finală aarcului ;
–nodurile xșiysunt adiacente ;
–arcul ușinodul xsunt incidente îngraf;
–arcul ușinodul ysunt incidente îngraf;
–nodul ysenumește succesor alluix;
–nodul xsenumește predecesor alluiy.
Definiție :
Unarcdeforma [x,x]senumește buclă .
Observație :
[x,y]≠[y,x]deoarece există oorientare aarcului

Exemplu .Fie G = ( X , U )
X = { 1 , 2 , 3 , 4, 5, 6 }
U = { [ 1 , 1 ], [ 1 , 6 ], [ 2 , 1 ], [ 2 , 3 ], [ 3 , 2 ], [ 2 , 4 ] , [ 3 , 4 ] , [ 5 , 4 ], [ 6 , 5 ], [ 4 , 6 ]}
[ 1 , 6] –arc (1 extremitate inițială, 6 extremitate finală)
6 –succesor al lui 1
1 -predecesor al lui 6
[ 1 , 1 ] –buclă
1
6
2
5
3
4

Definiție :
Gradul exterio r al unui vârf x, notat d +( x ), reprezintă numărul arcelor care iesdin nodul x, adică
numărul arcelor de forma [ x , y ] U.
Definiție :
Gradul interior al unui vârf x, notat d –( x ), reprezintă numărul arcelor care intră înnodul x, adică
numărul arcelor de forma [ y , x ] U.
1
6
2
5
3
4d +( 4) = 1
d +( 2) = 2
1
2
5
3
d -( 4) =3
d -( 6) = 2

Definiție :
+( x ) = { y X ( x , y ) U } –mulțimea succesorilor lui x
–( x ) = { y X ( y , x ) U } –mulțimea predecesorilor lui x
Exemplu :+( 2 ) = { 1 , 3 , 4 } –( 2 ) = { 3 }
Definiție :
+( x ) = { u = ( x , y ) u U } –mulțimea arcelor care iesdinnodul x
–( x ) = { u = ( y , x ) u U } –mulțimea arcelor care intră înnodul x
Exemplu :
+( 2 ) = { ( 2 , 1 ) , ( 2 , 3 ) , ( 2 , 4 ) }
–( 2 ) = { ( 3 , 2 ) }
1
6
2
5
3
4

Graf parțial. Subgraf
Definiție :
Fie graful G = ( X , U ). Un graf parțialal luiG, esteun grafG 1= ( X , V ) astfel încât V U, adică G1
are aceeași mulțime de noduri caG, iarmulțimea de arce V estechiar U sauo submulțime a acesteia .
X = { 1 , 2 , 3 , 4, 5, 6 }
U = {[1,1],[1,6],[2,1],[2,3],[3,2],[2,4],[3,4 ], [5,4], [6,5], [4,6]}
Grafparțial
X = { 1 , 2 , 3 , 4, 5, 6 }
U = {[1,1],[1,6],[2,1 ],[3,2],[2,4 ], [5,4],[4,6]}
1
6
2
5
3
4
1
6
2
5
3
4

Definiție :
Fie G = ( X , U ). Un subgraf al luiG, esteun grafG 1= ( Y , T ) astfel încât Y X, iarT conține toate
arcele din U care au ambele extremități înY ( se obține din G eliminând o parte din noduri șipăstrând acele arce
care au ambele extremități înmulțimea nodurilor rămase ).
X = { 1 , 2 , 3 , 4 , 5, 6 }
U = {[1,1],[1,6],[2,1],[2,3],[3,2],[2,4],[3,4], [5,4], [6,5], [4,6]}
Subgraf
X = { 1 , 2 , 3 , 6 }
U = {[1,1],[1,6],[2,1],[2,3],[3,2 ]}
1
6
2
3
1
6
2
5
3
4

Drum. Circuit
Definiție :
Se numește drum îngraful G, o succesiune de noduri D = ( z1, z2, … , zk), unde z1, z2, … , zkX,
astfel încât oricare două noduri consecutive sunt adiacente , adică [ z1, z2] , [ z2, z3] , … , [ zk–1, zk] U.
Nodurile z 1șiz kse numesc extremitățile drumului .
Numărul de arce care intră încomponența sa reprezintă lungimea drumului .
Dacă nodurile z1, z2, … , zksunt distincte două câtedouă , drumul se numește elementar . Încaz
contrar , drumul se numește neelementar .
Exemplu .Fie G = ( X , U )
X = { 1 , 2 , 3 , 4, 5, 6 }
U = { [ 1 , 1 ], [ 1 , 6 ], [ 2 , 1 ], [ 2 , 3 ], [ 3 , 2 ], [ 2 , 4 ] , [ 3 , 4 ] , [ 5 , 4 ], [ 6 , 5 ], [ 4 , 6 ] }
1
6
2
5
3
4D1= (1, 6, 5, 4) –drum elementar de lungime 3
D2= (2, 3, 4, 6, 5, 4) –drum neelementar de lungime 5

Definiție :
Se numește circuit într–un graf, un drum D = ( z1, z2, … , zk) cuproprietatea
căz1= zkșiarcele [ z1, z2] , [ z2, z3] , … , [ zk–1, zk] sunt distincte două câtedouă .
Dacă într–un circuit, toate nodurile cuexcepția primului șia ultimului sunt
distincte două câtedouă , atunci circuitul se numește elementar . Încazcontrar , circuitul
se numește neelementar .
Exemplu .Fie G = ( X , U )
X = { 1 , 2 , 3 , 4, 5, 6 }
U = { [ 1 , 1], [ 1 , 6], [ 2 , 1], [ 2 , 3], [2 , 5], [3 , 2], [2 , 4] , [3 , 4] , [5 , 4], [6 , 2], [6 , 5], [4 , 6] }
C1= (4, 6, 5, 4) –circuit elementar de lungime 3
C2= (2, 3, 4, 6, 2) –circuit elementar de lungime 4
C3= (2, 3, 2, 4, 6, 2) –circuit neelementar de lungime 5
1
6
2
5
3
4

Reprezentarea grafurilor orientate
● Matricea de adiacență
a M n x n
𝑎𝑖,𝑗= 1,𝑑𝑎𝑐ă𝑒𝑥𝑖𝑠𝑡ă𝑎𝑟𝑐𝑑𝑒𝑙𝑎𝑖𝑙𝑎𝑗
0,î𝑛𝑐𝑎𝑧𝑐𝑜𝑛𝑡𝑟𝑎𝑟
1
6
2
5
3
41 2 3 4 5 6
1 1 0 0 0 0 1
2 1 0 1 1 1 0
3 0 1 0 1 0 0
4 0 0 0 0 0 1
5 0 0 0 1 0 0
6 0 1 0 0 1 0

● Liste de adiacență
1
6
2
5
3
4Pentru ungraf orientat cuG=(V,U) sevamemora numărul denoduri nșiapoi,pentru fiecare nod x,lista
succesorilor luix,adică nodurilor ycuproprietatea căexistă arcul (x,y).
Nod Lista succesorilor
1 6
2 1, 3, 4, 5
3 2, 4
4 6
5 4
6 2, 5

Graf complet. Graf turneu
Definiție :
FieG=(V, U) un graforientat . Graful Gse numește graf complet dacă oricare două vârfuri
distincte ale sale sunt adiacente .
Două vârfuri xșiysunt adiacente dacă:
între eleexistă arcul (x,y), sau
între eleexistă arcul (y,x), sau
între eleexistă arcele (x,y)și(y,x).
1
6
2
5
3
4Teoremă :
Numărul degrafuri orientate complete cunnoduri este3n*(n-1)/2.

Definiție :
Ungraf orientat este turneu ,dacă oricare arfidouă vârfuri ișij,i≠j,între eleexistă unsingur arc:arcul (i,j)sau
arcul (j,i).
1
6
2
5
3
4Proprietăți :
1.Orice grafturneu estegrafcomplet .
2.Avem 2n*(n-1)/2grafuri turneu cunnoduri .
3.Înorice grafturneu există un drum elementar care trece printoate
vârfurile grafului .

Conexitate . Tare conexitate
FieG=(V,U) ungraforientat .
Graful senumește conex dacă între oricare două noduri distincte există celpuțin unlanț.
Senumește componentă conexă unsubgraf conex șimaximal cuaceastă calitate (adică dacă ammaiadauga unnod,
n-armaificonex ).
Graful senumește tareconex dacă între oricare două noduri distincte există celpuțin undrum .
Senumește componentă tare conexă unsubgraf tareconex șimaximal cuaceastă calitate –dacă ammaiadauga un
nod, n-armaifitareconex .

Graf hamiltonian . Graf eulerian
Fieungraforientat G=(V,U) .
Undrum elementar care conține toate nodurile grafului senumește drum hamiltonian .
Uncircuit elementar care conține toate nodurile grafului senumește circuit hamiltonian .
Ungrafcare conține uncircuit hamiltonian senumește graf hamiltonian .
Undrum care conține toate arcele grafului senumește drum eulerian .
Uncircuit care conține toate arcele grafului senumește circuit eulerian .
Ungrafcare conține uncircuit eulerian senumește graf eulerian .
Teoremă :
Ungraffărănoduri izolate esteeulerian dacă șinumai dacă esteconex șipentru fiecare nod, gradul interior este
egal cucelexterior .