Szomszédsági mátrix

A Wikipédiából, a szabad enciklopédiából

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 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éldák[szerkesztés | forrásszöveg szerkesztése]

  • 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
6n-graph2.svg \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 Kr,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[szerkesztés | forrásszöveg szerkesztése]

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 ésG_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 :

P A_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 An 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[szerkesztés | forrásszöveg szerkesztése]

Egy egyszerű gráf Siedel szomszédsági mátrixa vagy (0,-1,1) szomszédsági mátrixa 0-t tartalmaz a főátlóban, az aij 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[szerkesztés | forrásszöveg szerkesztése]

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. 8 e 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 8 e > 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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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