naapurimatriisina

Naapurimatriisina viitataan graafiteoriassa käytettyyn naapurimatriisiin, jolla voidaan esittää graafin jäsenten välinen naapuruus. Tällainen matriisi kuvaa, miten suurin osa verkon yhteyksistä on järjestetty ja sitä käytetään erilaisten graafien ominaisuuksien tutkimiseen.

Määritelmä: Olkoon G = (V,E) graafi, jossa n = |V|. Olkoon A n × n -matriisi, jonka alkio a_ij on 1, jos solmujen v_i ja v_j välillä on kaari {v_i,v_j} ∈ E, ja 0 otherwise. Jos graafi on yksinkertainen ja suunnaton (ei silmukoita eikä monikaaria), A on symmetrinen ja diag on nolla. Jos silmukoita on, a_ii voi olla 1. Suunnatuissa graafeissa a_ij kertoo kaaren suunnan eikä matriisi ole välttämättä symmetrinen.

Painotettut ja muut variantit: Painotetuissa graafeissa a_ij vastaa kaaren painoa tai kapasiteettia; tyhjä kaari merkitään 0:lla. Normaalisoinnin tai muiden muotojen avulla matriisia voidaan käyttää erilaisten luonteiden, kuten todennäköisyyksien tai siirtymävakioiden, kuvaamiseen.

Ominaisuudet ja sovellukset: Rivin summa summaa a_ij:stä antaa solmun suunnan tai asteen (yksinkertaisessa graafissa astuu sama kuin deg(v_i)). Käyppäisit A^k antaa kävelyiden määrän pituudeltaan k: (A^k)_{ij} on joukkoja kävelyiden määrän solmujen v_i ja v_j välillä. Adjacency-matriisi on keskeinen työkalu spektraalisessa graafiteoriassa, verkon analysoinnissa, hakualgoritmeissa sekä monissa laskennallisissa menetelmissä.

Esimerkki: Neljällä solmulla ja reunoilla 1-2, 2-3, 3-4 adjoin-matriisi on:

0 1 0 0

1 0 1 0

0 1 0 1

0 0 1 0

Naapurimatriisina esittäminen on perusmenetelmä sekä verkkomallinnuksessa että algoritmeissa, joissa haetaan yhteyksiä, komponentteja tai kävelyverkostoja.