Reprezentarea grafurilor orientate
description
Transcript of Reprezentarea grafurilor orientate
Reprezentarea grafurilor orientate
Graf orientatSe numeste graf orientat o pereche ordonata
de multimi G=(x,u) unde x este o multime finita si nevida de elemente numita multimea
nodurilor sau a varfurilor,iar u este o multime formata din perechi ordonate din x
numita multimea arcelor sau a muchiilor.
Pentru reprezentarea grafurilor orientate se poate folosi:
Matricea drumurilor
Matricea de adiacenta
Vectorul arcelor
Vectorul de arce
Pentru un graf cu n varfuri si m arce ,vectorul de arce are ca numar de componente valoarea m.Fiecare element al sau fiind un arc care va reprezenta extremitatea finala si cea initiala
V={(1,2),(1,3),(2,3),(4,1),(4,2)}
1
2
3
4
Matricea drumurilor
Este o matrice patratica alea carei elemente sunt date de relatia : d(I,j)={1,daca nu apartine drumului de la i la j 0,daca apartine drumului de la i la j
2
3
641
5
Matricea de adiacenta
Matrice de adiacenta este o matice a cu n linii si n coloane,in care elementele a[i][j] se definesc astfel:
a[i,j]={1,daca exista arcul (i,j) in multimea u
0,in caz contrar 2
41
5 3