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

Из Википедије, слободне енциклопедије

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

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

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

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

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

Матрица повезаности А бипартитивног графа чији делови имају r и s тачке је облика 
A = \begin{pmatrix} 0_{r,r} & B \\ B^T & 0_{s,s} \end{pmatrix}, где је B r x s матрица, а 0 представља нула матрицу. Матрица B тако јединствено представља бипартитивне графове и често се зове матрица бипартитивне повезаности. Нека је G=(U,V,E) бипартитивни граф где је U=u1,...,ur и V=v1,...,vs. Матрица бипартитивне повезаности је r x s 0-1 матрица B у којој bi,j=1 ако и само ако (ui,vj) елементи Е.

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

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

Структуре података[уреди]

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

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

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

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

Пример[уреди]

Обележени граф Матрица повезаности
6n-graph2.svg \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


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