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ő eleme az i csúcsból a j csúcsba vezető élek száma, míg a főátlóban található , 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]

  • 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
  • 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:

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]

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, és-t , és szomszédsági mátrixaik , adottak. és izomorfak, akkor és csak akkor, ha létezik egy permutációmátrix amire :

.

Ekkor és 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 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.

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, a v = ( 1,1, …, 1) vektorhoz tartozó sajátértéke lesz A-nak, és összefüggő, ha multiplicitása 1. Látható, hogy 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]

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]

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 byte folyamatos helyet foglalnak el, ahol 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. byte tárhelyet igényel, ahol az élek száma.

Mivel egy egyszerű gráfnak legfeljebb éle lehet, (az esetleges hurokéleket is belevéve), így a 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 , azaz, amikor . 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]

  • 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]

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