naapurimatriisiin

Naapurimatriisi on graafeissa käytetty matriisi, joka kertoo, mitkä solmujen parit ovat naapureita. Olkoon G = (V,E) graafi, missä V = {v1, ..., vn} ja E on kaaret. Naapurimatriisi A on n×n-matriisi, jonka alkio Aij on määritelty seuraavasti: Aij = 1, jos solmujen i ja j välillä on kaari (vi,vj) ∈ E; Aij = 0 muuten. Painotetuissa grafioissa Aij on kaaren paino w(i,j).

Jos graafi on suunnattu, matriisi ei välttämättä ole symmetrinen; silloin Aij voi poiketa Aji. Yleensä yksinkertaisessa, suunnittelemattomassa grafissa ilman silmukoita Aii = 0 ja Aij ∈ {0,1}. Silmukoita (looppeja) sisältävissä grafissa Aii voi olla suurempi kuin 0.

Ominaisuudet ja tulkinnat: Rivin summa A:n rivillä i antaa solmun i painottamattoman asteen, kun grafi on yksinkertainen. Painotetuissa grafissa rivin summa vastaa solmun i painotettua astetta. Päättelyt varten A^k antaa tietoa: A^kij on lukumäärä kaikkien pituudeltaan k olevien polkujen, jotka johtavat solmusta i solmuun j. Tämä yhdistää adjacenssimatriisin kätevästi polku- ja käsiteanalyysiin.

Naapurimatriisi liittyy myös muihin grafi- ja lineaarialgebran välineisiin: degreematriisi D on diagonaalimatriisi, jonka i:nnen diagonaalinen alkio on solmun i asteen summa; Laplaced matriisi L = D − A kuvaa grafin rakennetta spektrisesti. Normalisoitu naapurimatriisi Ā = D^−1/2 A D^−1/2 on suosittu verkko- ja spektrialgebran sovelluksissa.

Esimerkkinä pienessä kolmiloopp graafissa A = [[0,1,0],[1,0,1],[0,1,0]].