Szomszédsági mátrix

A matematikában és a számítástechnikában egy véges irányított vagy irányítatlan n csúcsú G gráf szomszédsági mátrixa (ritkábban: adjacenciamátrixa) az az n × n-es mátrix, amelynek a nem a főátlóban szereplő $a_{ij}$ eleme az i csúcsból a j csúcsba vezető élek száma, míg a főátlóban található $a_{ii}$, vagy az i csúcsnál lévő hurkok számának kétszerese vagy csak a hurkok száma (az, hogy melyiket használjuk a matematikai felhasználástól függ. Ez a cikk az első sablont követi irányítatlan gráfok esetén, míg az irányított gráfoknál az utóbbit alkalmazzuk). Minden egyes gráfnak létezik egy egyedi szomszédsági mátrixa, mely nem szomszédsági mátrixa egyetlen más gráfnak sem – így a szomszédsági mátrix az adott gráf egy reprezentációjának tekinthető. A véges egyszerű gráfok speciális esetében a szomszédsági mátrix egy csupa 0-ból és 1-esekből álló mátrix 0-kkal a főátlóban. Ha a gráf irányítatlan, akkor a szomszédsági mátrixa szimmetrikus.

A gráfok egy másik reprezentációja az illeszkedési mátrix.

A gráf és a szomszédsági mátrixának sajátértékei és sajátvektorai közti kapcsolattal a spektrális gráfelmélet foglalkozik.

Páros gráf szomszédsági mátrixa

Egy páros gráf A szomszédsági mátrixa, ha a páros gráf partíciói r, illetve s csúcsból állnak, a következő alakban felírható:

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

ahol B egy r × s mátrix, 0_r,r és 0_s,s pedig r × r, illetve s × s méretű 0-kból álló mátrixokat jelölnek. Ebben az esetben a kisebb, B mátrix a gráf egyedi leképezését adja, ezért az A többi részét redundánsként elhagyhatjuk. Ebben az esetben a B-t páros-szomszédsági mátrixnak (angol nyelvterületen: biadjacency matrix) nevezik.

Példák

• Itt egy egyszerű példa egy címkézett gráfra és az ő szomszédsági mátrixára. Az itt követett eljárás az, hogy a hurokéleket 1-essel jelöljük az irányítatlan gráf mátrixában.

Címkézett gráf	Szomszédsági mátrix
	${\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}}$

• Egy teljes gráf szomszédsági mátrixa csupa 1-eseket tartalmaz a főátló kivételével.

• Egy K_r,s teljes páros gráfnak a szomszédsági mátrixa a következőképpen néz ki:

${\begin{pmatrix}O&J\\J^{T}&O\end{pmatrix}},$

ahol J egy r × s csupa 1-esekből álló mátrix, O pedig egy csupa 0-ból álló mátrixot jelöl.

Tulajdonságok

Egy irányítatlan gráf szomszédsági mátrixa szimmetrikus és ezért valós sajátértékeinek halmaza teljes, és ortogonális sajátvektor bázissal rendelkezik. A gráf sajátértékeinek halmaza a gráf spektruma.

Tegyük fel, hogy 2 irányított vagy irányítatlan gráf, $G_{1}$ és$G_{2}$-t , és szomszédsági mátrixaik $A_{1}$, $A_{2}$ adottak. $G_{1}$ és $G_{2}$ izomorfak, akkor és csak akkor, ha létezik egy permutációmátrix $P$ amire :

$PA_{1}P^{-1}=A_{2}\,$.

Ekkor $A_{1}$ és $A_{2}$ hasonlóak és ezért minimálpolinomjuk, karakterisztikus polinomjuk, sajátértékeik, determinánsuk és nyomuk megegyezik. Így ezek, gráfok izomorfia invariánsaként szolgálhatnak. Azonban az lehetséges, hogy 2 gráfnak ugyanazok a sajátértékei, és mégsem izomorfak.

Ha A a G irányított vagy irányítatlan gráf szomszédsági mátrixa, akkor az Aⁿ mátrix (n db A-nak a mátrixszorzata) rendelkezik egy érdekes értelmezéssel: Az i. sor j. eleme megadja az i csúcsból a j csúcsba menő irányított vagy irányítatlan n hosszúságú séták számát.

Az (I ‒ A) mátrix (ahol I az n × n-es egységmátrix) invertálható, akkor és csak akkor, ha nincs irányított kör a G gráfban. Ebben az esetben az $(I-A)^{-1}$ inverzének a következő értelmezése van:Az i. sor j. eleme megadja az i csúcsból a j csúcsba menő lehetséges irányított útvonalak számát. ( Ami mindig véges, ha nincs irányított kör) Ez a mátrixok geometriai sorát alkalmazva érthető meg.

$(I-A)^{-1}=I+A+A^{2}+A^{3}+...\,$

Felhasználva, hogy az i-ből a j-be menő útvonalak száma megegyezik a 0 hosszúságú útvonalak számának, az 1 hosszúságú útvonalak számának, a 2 hosszúságú útvonala számának stb. összegével.

Minden hurokélmentes gráfnak megfelelő szomszédsági mátrix főátlója csak 0 elemekből áll.

A (d)-reguláris gráfok esetén, $d$ a v = ( 1,1, …, 1) vektorhoz tartozó sajátértéke lesz A-nak, és $G$ összefüggő, ha $d$ multiplicitása 1. Látható, hogy $-d$ szintén sajátértéke A-nak, ha G összefüggő páros gráf. A fentiek a Perron–Frobenius-tétel következményei.

Variánsok

Egy egyszerű gráf Seidel-féle szomszédsági mátrixa vagy (0,-1,1) szomszédsági mátrixa 0-t tartalmaz a főátlóban, az a_ij eleme pedig = -1 ha ij él, és = +1 ha nem az. Ezt a mátrixot használják az erősen reguláris gráfok és a kettős gráfok vizsgálatánál.

A távolsági mátrix olyan mint egy magasabb szintű szomszédsági mátrix. Ahelyett, hogy csak arról nyújtana információt, hogy két csúcs össze van-e kötve, vagy nincs, megadja a távolságot is közöttük. Ez azt feltételezi, hogy minden él hossza 1. Létezik olyan fajtája is, amikor az élek hossza nem feltétlenül 1.

Adatstruktúrák

Adatstruktúraként történő felhasználáskor a szomszédsági mátrix helyett még éllistát szokás használni. Mivel a szomszédsági mátrix minden egyes eleme csak egy bitet igényel, így nagyon tömören le lehet írni a mátrix elemeit – csak ${n^{2}}/8$ byte folyamatos helyet foglalnak el, ahol $n$ a csúcsok száma. A helyveszteség elkerülésén túl ez a kompaktság lehetővé teszi a hivatkozás helyét.

Másfelől egy ritka gráfnál jobbak az éllisták, mert nem használnak helyet a nem létező élek tárolására. Egy egyszerű (sorba)rendezési alkalmazás használatával egy 32 bites számítógépen egy irányítatlan gráf szomszédsági listája kb. $8e$ byte tárhelyet igényel, ahol $e$ az élek száma.

Mivel egy egyszerű gráfnak legfeljebb $n^{2}$ éle lehet, (az esetleges hurokéleket is belevéve), így a $d=e/n^{2}$ formulával kifejezhetjük a gráf sűrűségét. Vagyis az éllistás megadás akkor foglal több helyet a mátrixosnál, ha $8e>n^{2}/8$, azaz, amikor $d>1/64$. Ezért a gráfnak tényleg ritkának kell lennie, hogy indokolt legyen a szomszédsági lista használata.

A helyigény figyelembevétele mellett, a különböző adatstruktúrák különböző műveleteket is lehetővé tesznek. Megtalálni valamennyi olyan csúcsot, ami az éllistában szereplő egyik csúccsal szomszédos, olyan egyszerű, mint csak elolvasni a listát. Egy szomszédsági mátrix esetében egy egész sort végig kell ellenőrizni, ami O(n) időt vesz igénybe. Azt hogy van-e él két adott csúcs között, egyből meg lehet határozni egy szomszédsági mátrix esetében, miközben ez az éllista esetében a két csúcs fokszámainak minimumával arányos időt vesz igénybe.

Hivatkozások

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001), Introduction to Algorithms, second edition. MIT Press and McGraw-Hill. ISBN 0-262-03293-7. Section 22.1: Representations of graphs, pp. 527–531.

• Chris Godsil and Gordon Royle (2001), Algebraic Graph Theory. New York: Springer-Verlag. ISBN 0-387-95241-1

• Katona, Recski, Szabó, A számítástudomány alapjai, Typotex, Budapest, 2006. 31-32. o.

Külső hivatkozások

• Fluffschack — an educational Java web start game demonstrating the relationship between adjacency matrices and graphs.