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ő Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): a_{{ij}} eleme az i csúcsból a j csúcsba vezető élek száma, míg a főátlóban található Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): 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]

  • 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 Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): {\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:
Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {\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]

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, Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): G_{1} ésÉrtelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): G_{2} -t , és szomszédsági mátrixaik Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): A_{1} , Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): A_{2} adottak. Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): G_{1} és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): G_{2} izomorfak, akkor és csak akkor, ha létezik egy permutációmátrix Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): P amire :

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): PA_{1}P^{{-1}}=A_{2}\, .

Ekkor Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): A_{1} és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): 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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): (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.

Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): (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, Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): d a v = ( 1,1, …, 1) vektorhoz tartozó sajátértéke lesz A-nak, és Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): G összefüggő, ha Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): d multiplicitása 1. Látható, hogy Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): -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]

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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): {n^{2}}/8 byte folyamatos helyet foglalnak el, ahol Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): 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. Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): 8e byte tárhelyet igényel, ahol az élek száma.

Mivel egy egyszerű gráfnak legfeljebb Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): n^{2} éle lehet, (az esetleges hurokéleket is belevéve), így a Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): 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 Értelmezés sikertelen (MathML SVG vagy PNG tartalékkal (modern böngészők és kisegítő eszközök számára ajánlott): Érvénytelen válasz („Math extension cannot connect to Restbase.”) a(z) /mathoid/local/v1/ szervertől:): 8e>n^{2}/8 , azaz, amikor Értelmezés sikertelen (Átalakítási hiba. A szerver („https://hu.wikipedia.org/api/rest_”) a következőt jelentette: „Cannot get mml. Server problem.”): 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]

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