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 Mij = 0 ako čvorovi i i j nisu susedni, Mij = 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.

Valid XHTML 1.0 Strict! | Site map | Kontakt | © 2007..2015 prof. Duško Obradović sa učenicima Gimnazije