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

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

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

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

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

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

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

Матрица повезаности А бипартитивног графа чији делови имају r и s тачке је облика

где је B матрица величине r × s, а 0 представља нула матрицу. Матрица B тако јединствено представља бипартитивне графове и често се зове матрица бипартитивне повезаности. Нека је G = (U,V,E) бипартитивни граф где је U = {u1, …, ur} и V = {v1, …, vs}. Матрица бипартитивне повезаности је r × s 0–1 матрица B у којој bi,j = 1 ако и само ако су (ui,vj) елементи Е.

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

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

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

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

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

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

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

Пример[уреди | уреди извор]

Обележени граф Матрица повезаности
6n-graph2.svg

Координате су 1–6

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

Референце[уреди | уреди извор]

  1. ^ Programiranje 2, Matematički fakultet Beograd, Jelena Tomašević
  2. ^ Konstrukcija i analiza algoritama, Nina Radojčić
  3. ^ Konstrukcija i analiza algoritama, Anja Bukurov, Nikola Ajzenhamer, Vojislav Stanković

Спољашње везе[уреди | уреди извор]