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

Računarstvo i Informatika

Grafovi

Predstavljanje grafa

Najčešće se grafovi predstavljaju na dva načina:

1. Preko liste povezanosti
2. Preko matrice susedstva.

Za graf dimenzije N i broja veza m, preko matrica susedstva, potreban je N² memorijskog prostora, dok preko liste povezanosti treba samo N + m.

Odluka o načinu predstavljanja grafa zavisi od nekoliko stvari:

• Da li je poznat broj veza. Ako nije koristimo matricu susedstva.
• Da li je N + m mnogo manje od N². Ako jeste koristimo listu povezanosti.
• Da li su algoritmi koje nameravamo upotrebiti radi rešavanja problema uz upotrebu određenog načina interpretacije grafa dovoljno jednostavni, efikasni i sl.

Za graf dimenzije N, matrica susedstva, A je kvadratna matrica dimenzije NxN, takva da A_ij = 0 ako čvorovi i i j nisu susedni, = 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.