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