Gradivo za takmičenje u Gimnaziji "Veljko Petrović"

Računarstvo i Informatika

Grafovi

Predstavljanje grafa - Matrica susedstva

Ovaj način predstavljanja grafova je lakše a kasnije ćemo videti i relativno lak za obradu, način predstavljanja grafa je preko matrice susedstva.

Kada se koristi ovaj način, tada je graf G predstavljen kao ureੱeni par (N i M[nxn]). Deklaracioni deo:

Const MaxN = ???;

Type TGraf = Record

               N : LongInt;

               M : array [1..MaxN, 1..MaxN] of Longint;

             End;

Type TCvor = 0..MaxN;

Var G : TGraf;

Za graf dimenzije N, matrica susedstva, M je kvadratna matrica dimenzije NxN, takva da M_ij = 0 ako čvorovi i i j nisu susedni, M_ij = 1 ako su čvorovi i i j susedni.

Ako je čvor x susedan čvoru y tada važi i obrnuto, a to znači da je matrica susedstva simetrična.

Stepen čvora se sada dobije lako, tako što prebrojimo elemente u odgovarajućem redu koji su > 0.