У теорији графова и рачунарству, матрица повезаности или матрица суседства је начин репрезентације међусобне повезаности тачака (или чворова) графа. Постоји још један матрична репрезентација графа и зове се матрица инциденције.
Матрица повезаности коначног графа G са n чворова је n x n (квадратна) матрица где је аij број грана од тачке i до тачке j, док аii представља број грана које иду из тачке i у саму њу.Programiranje 2 , Matematički fakultet Beograd, Jelena Tomašević Тачније, то је квадратна матрица, симетрична у односу на главну дијагоналу. У посебном случају коначног графа, матрица повезаности је Булова матрица са нулама на дијагонали. Ако постоји грана између два чвора од vi до чвора vj онда је аij = 1, док су сви остали елементи нуле. Ако је граф неусмерен, матрица повезаности је симетрична.Konstrukcija i analiza algoritama, Nina Radojčić Матрица суседства је матрица која на позицији пресека 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-ту тачку са ј-том тачком.
Структуре података За коришћење као структура података, главна алтернатива матрице повезаности је листа повезаности.Konstrukcija i analiza algoritama , Anja Bukurov, Nikola Ajzenhamer, Vojislav Stanković Пошто сваки унос у матрицу повезаности захтева само један бит, може се приказати много компактније заузимајући само n2/8 бајтова меморије, где је n број тачака. Осим што се овим избегава неискоришћен простор, ово подједностављење води до локалности референци. Користећи итеративну имплементацију низом на 32-битном рачунару, листа повезаности за неусмерени граф захтева око 8е бајтова, где је е број грана.
С обзиром да граф може да има до n2 грана укључујући и гране које улазе у исту тачку из које крећу, густина графа се може записати као d = e/n2. Одатле следи да репрезентација листе повезаности, 8e > n2/8, заузима више меморије када је d > 1/64.
Проналажење свих суседних тачака дате тачке у листи повезаности је једноставно колико и само читање листе. Код матрице повезаности, прво се мора проћи кроз цео један ред што траје .
У случају да је граф неусмерен, скоро 50% меморије можемо уштедети ако се памте само елементи испод или изнад главне дијагонале, јер је матрица симетрична.
Пример Обележени графМатрица повезаности200pxКоординате су 1–6
Матрица повезаности комплетаног графа садржи све јединице осим дуж дијагонале где су само нуле. Матрица повезаности празног графа је нула матрица
Референце
Спољашње везе
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.
Категорија:Структуре података графа Категорија:Теорија графова Категорија:Матрице