Matrica povezanosti

U teoriji grafova i računarstvu, matrica povezanosti ili matrica susedstva je način reprezentacije međusobne povezanosti tačaka (ili čvorova) grafa. Postoji još jedan matrična reprezentacija grafa i zove se matrica incidencije.

Matrica povezanosti konačnog grafa G sa n čvorova je n x n (kvadratna) matrica gde je a_ij broj grana od tačke i do tačke j, dok a_ii predstavlja broj grana koje idu iz tačke i u samu nju. Tačnije, to je kvadratna matrica, simetrična u odnosu na glavnu dijagonalu. U posebnom slučaju konačnog grafa, matrica povezanosti je Bulova matrica sa nulama na dijagonali. Ako postoji grana između dva čvora od v_i do čvora v_j onda je a_ij = 1, dok su svi ostali elementi nule. Ako je graf neusmeren, matrica povezanosti je simetrična. Matrica susedstva je matrica koja na poziciji preseka i-te vrste i j-te kolone sadrži 1, ako je i-ti čvor spojen sa j-tim čvorom. Inače je 0.

Matrice povezanosti zahtevaju n² (gde je n broj tački) memorije, bez obzira koliko je broj grana u grafu. To znači da koriste dosta memorijskog prostora i veoma su nepraktične za grafove sa malim brojem grana što je u praksi čest slučaj.

Odnos između grafa i sopstvenih vrednosti i vektora matrice povezanosti se izučava u oblasti spektralne teorije grafova.

Matrica povezanosti bipartitivnog grafa

Matrica povezanosti A bipartitivnog grafa čiji delovi imaju r i s tačke je oblika $A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},$

gde je B matrica veličine r × s, a 0 predstavlja nula matricu. Matrica B tako jedinstveno predstavlja bipartitivne grafove i često se zove matrica bipartitivne povezanosti. Neka je G = (U,V,E) bipartitivni graf gde je U = {u₁, …, u_r} i V = {v₁, …, v_s}. Matrica bipartitivne povezanosti je r × s 0–1 matrica B u kojoj b_i,j = 1 ako i samo ako su (u_i,v_j) elementi E.

Ako je G bipartitivni graf onda su elementi b_i,j brojevi grana između tačaka ili težine grane (u_i,v_j).

Matrice povezanosti mogu da se koriste i za grafove kao i multigrafove. Tada na poziciju preseka i-te vrste i j-te kolone treba staviti broj grana koje spajaju i-tu tačku sa j-tom tačkom.

Strukture podataka

Za korišćenje kao struktura podataka, glavna alternativa matrice povezanosti je lista povezanosti. Pošto svaki unos u matricu povezanosti zahteva samo jedan bit, može se prikazati mnogo kompaktnije zauzimajući samo n²/8 bajtova memorije, gde je n broj tačaka. Osim što se ovim izbegava neiskorišćen prostor, ovo podjednostavljenje vodi do lokalnosti referenci. Koristeći iterativnu implementaciju nizom na 32-bitnom računaru, lista povezanosti za neusmereni graf zahteva oko 8e bajtova, gde je e broj grana.

S obzirom da graf može da ima do n² grana uključujući i grane koje ulaze u istu tačku iz koje kreću, gustina grafa se može zapisati kao d = e/n². Odatle sledi da reprezentacija liste povezanosti, 8e > n²/8, zauzima više memorije kada je d > 1/64.

Pronalaženje svih susednih tačaka date tačke u listi povezanosti je jednostavno koliko i samo čitanje liste. Kod matrice povezanosti, prvo se mora proći kroz ceo jedan red što traje $O(n)$.

U slučaju da je graf neusmeren, skoro 50% memorije možemo uštedeti ako se pamte samo elementi ispod ili iznad glavne dijagonale, jer je matrica simetrična.

Primer

Obeleženi graf	Matrica povezanosti
	${\begin{pmatrix}1&1&0&0&1&0\\1&0&1&0&1&0\\0&1&0&1&0&0\\0&0&1&0&1&1\\1&1&0&1&0&0\\0&0&0&1&0&0\\\end{pmatrix}}$ Koordinate su 1–6

• Matrica povezanosti kompletanog grafa sadrži sve jedinice osim duž dijagonale gde su samo nule.
• Matrica povezanosti praznog grafa je nula matrica

Spoljašnje veze

• Weisstein, Eric W. „Adjacency matrix”. MathWorld. 
• Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.
• Open Data Structures - Section 12.1 - AdjacencyMatrix: Representing a Graph by a Matrix, Pat Morin
• Café math : Adjacency Matrices of Graphs : Application of the adjacency matrices to the computation generating series of walks.