Матрица повезаности

У теорији графова и рачунарству, матрица повезаности или матрица суседства је начин репрезентације међусобне повезаности тачака (или чворова) графа. Постоји још један матрична репрезентација графа и зове се матрица инциденције.

Матрица повезаности коначног графа G са n чворова је n x n (квадратна) матрица где је а_ij број грана од тачке i до тачке j, док а_ii представља број грана које иду из тачке i у саму њу. Тачније, то је квадратна матрица, симетрична у односу на главну дијагоналу. У посебном случају коначног графа, матрица повезаности је Булова матрица са нулама на дијагонали. Ако постоји грана између два чвора од v_i до чвора v_j онда је а_ij = 1, док су сви остали елементи нуле. Ако је граф неусмерен, матрица повезаности је симетрична. Матрица суседства је матрица која на позицији пресека i-те врсте и ј-те колоне садржи 1, ако је i-ти чвор спојен са ј-тим чвором. Иначе је 0.

Матрице повезаности захтевају n² (где је n број тачки) меморије, без обзира колико је број грана у графу. То значи да користе доста меморијског простора и веома су непрактичне за графове са малим бројем грана што је у пракси чест случај.

Однос између графа и сопствених вредности и вектора матрице повезаности се изучава у области спектралне теорије графова.

Матрица повезаности бипартитивног графа

Матрица повезаности А бипартитивног графа чији делови имају r и s тачке је облика $A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},$

где је B матрица величине r × s, а 0 представља нула матрицу. Матрица B тако јединствено представља бипартитивне графове и често се зове матрица бипартитивне повезаности. Нека је G = (U,V,E) бипартитивни граф где је U = {u₁, …, u_r} и V = {v₁, …, v_s}. Матрица бипартитивне повезаности је r × s 0–1 матрица B у којој b_i,j = 1 ако и само ако су (u_i,v_j) елементи Е.

Ако је G бипартитивни граф онда су елементи b_i,j бројеви грана између тачака или тежине гране (u_i,v_j).

Матрице повезаности могу да се користе и за графове као и мултиграфове. Тада на позицију пресека i-те врсте и ј-те колоне треба ставити број грана које спајају i-ту тачку са ј-том тачком.

Структуре података

За коришћење као структура података, главна алтернатива матрице повезаности је листа повезаности. Пошто сваки унос у матрицу повезаности захтева само један бит, може се приказати много компактније заузимајући само n²/8 бајтова меморије, где је n број тачака. Осим што се овим избегава неискоришћен простор, ово подједностављење води до локалности референци. Користећи итеративну имплементацију низом на 32-битном рачунару, листа повезаности за неусмерени граф захтева око 8е бајтова, где је е број грана.

С обзиром да граф може да има до n² грана укључујући и гране које улазе у исту тачку из које крећу, густина графа се може записати као d = e/n². Одатле следи да репрезентација листе повезаности, 8e > n²/8, заузима више меморије када је d > 1/64.

Проналажење свих суседних тачака дате тачке у листи повезаности је једноставно колико и само читање листе. Код матрице повезаности, прво се мора проћи кроз цео један ред што траје $O(n)$.

У случају да је граф неусмерен, скоро 50% меморије можемо уштедети ако се памте само елементи испод или изнад главне дијагонале, јер је матрица симетрична.

Пример

Обележени граф	Матрица повезаности
	${\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}}$ Координате су 1–6

• Матрица повезаности комплетаног графа садржи све јединице осим дуж дијагонале где су само нуле.
• Матрица повезаности празног графа је нула матрица

Спољашње везе

• 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.