Vierekkäisyysmatriisi

Vierekkäisyysmatriisi on yksi tapa esittää kuvaaja matriisina.

Määritelmä

Graafin , jossa on äärellinen määrä pisteitä (numeroitu 1 - ) vierekkäisyysmatriisi on kooltaan neliömäinen kokonaislukumatriisi , jossa elementin arvo on yhtä suuri kuin reunojen lukumäärä graafin : nnesta kärjestä : nteen kärkeen. $G$ $n$ $n$ ${\mathbf A}$ $n\ kertaa n$ $a_{i,j}$ $i$ $j$

Joskus, varsinkin suuntaamattoman graafin tapauksessa, silmukka (särmä -: nnestä kärjestä itsestään) lasketaan kahdeksi reunaksi, eli diagonaalielementin arvo on tässä tapauksessa kaksinkertainen ympärillä olevien silmukoiden lukumäärään. -th vertex. $i$ ${\displaystyle a_{i,i))$ $i$

Yksinkertaisen graafin (jossa ei ole silmukoita tai useita reunoja) vierekkäisyysmatriisi on binäärimatriisi ja sisältää nollia päädiagonaalissa .

Kaksiosaisen graafin viereisyysmatriisi

Kaksiosaisen graafin vierekkäisyysmatriisi , jonka osilla on myös pisteitä , voidaan kirjoittaa seuraavaan muotoon ${\mathbf A}$ $r$ $s$

\mathbf {A} ={\begin{pmatrix}\mathbf {0} _{r,r}&\mathbf {B} \\\mathbf {B} ^{T}&\mathbf {0} _ {s,s}\end{pmatrix}},

missä on matriisi, ja ja ovat nollamatriiseja . Tässä tapauksessa pienempi matriisi edustaa yksiselitteisesti kuvaajaa, ja loput matriisin osat voidaan hylätä. kutsutaan joskus bis-viereisyysmatriiksi. $\mathbf {B}$ $r\times s$ ${\displaystyle \mathbf {0} _{r,r))$ $\mathbf {0} _{s,s}$ $r\times r$ $s\ kertaa s$ $\mathbf {B}$ ${\mathbf A}$ $\mathbf {B}$

Muodollisesti anna olla kaksiosainen kaavio , jossa on osat ja . Bikonjugaattimatriisi on 0–1 matriisi , jossa jos ja vain jos . $G=(U,V,E)$ $U=\{u_{1},\dots ,u_{r}\}$ $V=\{v_{1},\dots ,v_{s}\}$ $r\times s$ $\mathbf {B}$ $b_{i,j}=1$ $(u_{i},v_{j})\in E$

Jos on kaksiosainen multigrafi tai painotettu graafi, niin elementit ovat kärkien välisten reunojen lukumäärä tai vastaavasti reunojen painot . $G$ ${\näyttötyyli b_{i,j))$ ${\näyttötyyli (u_{i},v_{j})}$

Esimerkkejä

Alla on esimerkki suuntaamattomasta graafista ja sitä vastaavasta viereisyysmatriisista . Tämä graafi sisältää silmukan kärjen 1 ympärillä, ja tietyistä sovelluksista riippuen elementtiä voidaan pitää yhtä suurena kuin yksi (kuten alla on esitetty) tai kaksi. ${\mathbf A}$ $a_{1,1}$

Kaavio	Vierekkäisyysmatriisi
	${\displaystyle {\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)$

$a_{i,j}$ on kärkipisteitä ja , yhdistävien reunojen lukumäärä , ja joissakin sovelluksissa jokainen silmukka ( joillekin reuna ) lasketaan kahdesti. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $i$

Tyhjän graafin, jossa ei ole reunoja, vierekkäisyysmatriisi koostuu kaikista noloista.

Ominaisuudet

Suuntaamattoman graafin vierekkäisyysmatriisi on symmetrinen , mikä tarkoittaa, että sillä on todellisia ominaisarvoja ja ortogonaalinen ominaisvektorikanta. Sen ominaisarvojen joukkoa kutsutaan graafin spektriksi , ja se on spektrigraafiteorian pääasiallinen tutkimuskohde .

Kaksi kuvaajaa ja vierekkäisyysmatriiseja ja ovat isomorfisia silloin ja vain, jos on olemassa sellainen permutaatiomatriisi , $G_{1}$ $G_{2}$ $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$

{\displaystyle \mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2))

Tästä seuraa, että matriisit ja ovat samankaltaisia , ja siksi niillä on yhtäläiset ominaisarvot, determinantit ja ominaispolynomit. Päinvastoin ei kuitenkaan aina ole totta - kaksi kuvaajaa, joilla on samanlaiset vierekkäisyysmatriisit, eivät välttämättä ole isomorfisia (tämä tapahtuu, jos matriisi ei ole permutoitavissa, esimerkiksi matriisit ja ovat samanlaisia, mutta vastaavat graafit eivät ole isomorfisia). $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Matrix powers

Jos on graafin vierekkäisyysmatriisi , niin matriisilla on seuraava ominaisuus: -:nnen rivin -:nnen sarakkeen elementti on yhtä suuri kuin polkujen lukumäärä -: nnestä kärjestä -: nneen, ja se koostuu täsmälleen reunoista. ${\mathbf A}$ $G$ $\mathbf {A} ^{m}$ $i$ $j$ $i$ $j$ $m$

Tietorakenne

Viereisyysmatriisi ja viereisyysluettelot ovat tärkeimmät tietorakenteet , joita käytetään kuvaamaan tietokoneohjelmissa.

Vierekkäisyysmatriisin käyttö on suositeltavaa vain ei-harvoissa graafisissa, joissa on suuri määrä reunoja, koska se vaatii yhden databitin tallentamisen jokaista elementtiä kohden. Jos graafi on harva, suurin osa muistista menee hukkaan nollien tallentamiseen, mutta ei-harvassa graafissa vierekkäisyysmatriisi esittää graafin muistissa melko kompaktisti, käyttäen noin vähän muistia, mikä voi olla järjestys suuruusluokkaa parempi kuin vierekkäisyysluettelot. $n^{2}$

Painotettujen graafien kanssa toimivissa algoritmeissa (esimerkiksi Floyd-Warshall-algoritmissa ) vierekkäisyysmatriisin elementit sisältävät usein reunan olemassaolon tai puuttumisen osoittavien numeroiden 0 ja 1 sijasta reunojen painot. itse. Samanaikaisesti puuttuvien reunojen tilalle laitetaan jokin erityinen raja-arvo ( englanniksi sentinel ) ratkaistavasta ongelmasta riippuen, yleensä 0 tai . $\infty$

Katso myös

Kirjallisuus

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M .: Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .

Linkit

Graafisen viereisyysmatriisi. Ohjelmakoodi Pascalissa ja C++:ssa