Viereisyysmatriisi - Adjacency matrix

In graafiteoria ja tietotekniikan , vierusmatriisi on neliömatriisi käytetään edustamaan rajallinen kaavio . Elementtien matriisin ilmoittaa, onko paria pisteiden ovat vierekkäisten tai ei kaaviossa.

Äärimmäisen yksinkertaisen kuvaajan erikoistapauksessa vierekkäismatriisi on (0,1) -matriisi , jonka lävistäjä on nolla. Jos kuvaaja ei ole suunnattu (eli kaikki sen reunat ovat kaksisuuntaisia), vierekkäisyysmatriisi on symmetrinen . Kaavion ja sen vierekkäismatriisin ominaisarvojen ja ominaisvektorien välistä suhdetta tutkitaan spektrikäyräteoriassa .

Graafin vierekkäismatriisi on erotettava sen esiintyvyysmatriisista , erilaisesta matriisiesityksestä, jonka elementit osoittavat, ovatko piste -reuna -parit sattuvia vai eivät, ja sen matriisimatriisista , joka sisältää tietoja kunkin kärkipisteen asteesta .

Määritelmä

Yksinkertaiselle kuvaajalle, jonka kärkipistejoukko U = { u ₁ ,…, u _n }, vierekkäismatriisi on neliö n × n matriisi A siten, että sen elementti A _ij on yksi, kun on reuna pisteestä u _i pisteeseen u _j ja nolla, kun reunaa ei ole. Matriisin diagonaalielementit ovat kaikki nollaa, koska reunat pisteestä itseensä ( silmukat ) eivät ole sallittuja yksinkertaisissa kaavioissa. On myös joskus hyödyllistä algebrallisessa kuvaajateoriassa korvata nollasta riippumattomat elementit algebrallisilla muuttujilla. Sama käsite voidaan laajentaa koskemaan monikuvauksia ja kaavioita tallentamalla reunojen lukumäärä kunkin kahden kärkipisteen välille vastaavassa matriisielementissä ja sallimalla ei -nolla -diagonaaliset elementit. Silmukat voidaan laskea joko kerran (yksittäisenä reunana) tai kahdesti (kahdena piste-reunan esiintymänä), kunhan noudatetaan johdonmukaista käytäntöä. Ohjaamattomat kuvaajat käyttävät usein jälkimmäistä laskentasilmukoiden laskentatapaa kahdesti, kun taas suunnatut kuvaajat käyttävät tyypillisesti ensimmäistä käytäntöä.

Kaksiosainen kuvaaja

Kaksiosaisen kuvaajan vierekkäismatriisi A , jonka kahdessa osassa on r ja s kärki, voidaan kirjoittaa muodossa

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

jossa B on r × s -matriisi ja 0 _{r , r} ja 0 _{s , s} edustavat r × r- ja s × s -nollamatriiseja. Tässä tapauksessa pienempi matriisi B edustaa ainutlaatuisesti kuvaajaa, ja A: n muut osat voidaan hylätä tarpeettomina. B: tä kutsutaan joskus biadjacency -matriisiksi .

Muodollisesti, anna G = ( U , V , E ) on kaksijakoinen verkko osien U = { u ₁ , ..., u _r }, V = { v ₁ , ..., v _n } ja reunat E . Biadjacency matriisi on r x : n 0-1 matriisi B , jossa b _{i , j} = 1 , jos ja vain jos ( u _i , v _j ) ∈ E .

Jos G on kahden osapuolen monikuvaaja tai painotettu kuvaaja , elementeillä b _{i, j} katsotaan pisteiden välisten reunojen lukumäärä tai reunan paino ( u _i , v _j ) .

Muunnelmat

( , B , c ) -adjacency matriisi yksinkertainen kaavio on _{i , j} = jos ( i , j ) on reuna, b , jos se ei ole, ja c lävistäjä. Seidel vierusmatriisi on (-1, 1, 0) -adjacency matriisi. Tätä matriisia käytetään voimakkaasti säännöllisten ja kahden kuvaajan tutkimiseen .

Etäisyys matriisi on asennossa ( i , j ) välinen etäisyys pisteiden v _i ja v _j . Etäisyys on pisteitä yhdistävän lyhyimmän polun pituus. Ellei reunojen pituuksia ole nimenomaisesti ilmoitettu, polun pituus on sen reunojen määrä. Etäisyysmatriisi muistuttaa vierekkäisen matriisin suurta tehoa, mutta sen sijaan, että se kertoisi vain, onko kaksi huippua kytketty vai ei (eli yhteysmatriisi, joka sisältää boolen arvoja ), se antaa tarkan etäisyyden niiden välillä.

Esimerkkejä

Ohjaamattomat kaaviot

Tässä noudatettu käytäntö (suunnattamattomille kaavioille) on, että jokainen reuna lisää yhden matriisin oikeaan soluun ja jokainen silmukka lisää 2. Tämä mahdollistaa kärkipisteen asteen löytämisen helposti ottamalla joko sen arvojen summan vastaava rivi tai sarake vierekkäismatriisissa.

Merkitty kaavio	Viereisyysmatriisi
	${\ displaystyle {\ begin {pmatrix} 2 & 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}}$ Koordinaatit ovat 1–6.
Nauru -kaavio	Koordinaatit ovat 0–23. Valkoiset kentät ovat nollia, värilliset kentät ovat yhtä.

Suunnatut kaaviot

Suunnatun kuvaajan vierekkäismatriisi voi olla epäsymmetrinen. Suunnatun kuvaajan vierekkäismatriisi voidaan määritellä joko sellaiseksi

1. ei-nolla-elementti _ij osoittaa reunan i ja j tai
2. se osoittaa reunan j ja i .

Edellistä määritelmää käytetään yleisesti graafiteoriassa ja sosiaalisten verkostojen analysoinnissa (esim. Sosiologia, valtiotiede, talous, psykologia). Jälkimmäinen on yleisempi muissa soveltavissa tieteissä (esim. Dynaamiset järjestelmät, fysiikka, verkkotiede), joissa A: ta käytetään joskus kuvaamaan lineaarista dynamiikkaa kaavioissa.

Ensimmäisen määritelmän avulla kärkipisteen asteet voidaan laskea laskemalla yhteen vastaavan sarakkeen merkinnät ja pisteen ulosaste laskemalla yhteen vastaavan rivin merkinnät. Toista määritelmää käytettäessä kärkipisteen aste ilmoitetaan vastaavalla rivisummalla ja ulos-aste vastaavalla sarakesummalla.

Merkitty kaavio	Viereisyysmatriisi
Ohjaaja Cayley kuvaaja on S- 4	Koordinaatit ovat 0–23. Kun kuvaaja on suunnattu, matriisi ei välttämättä ole symmetrinen .

Triviaalit kaaviot

Täydellisen kuvaajan vierekkäismatriisi sisältää kaikki paitsi diagonaalia pitkin, jossa on vain nollia. Tyhjän kuvaajan vierekkäismatriisi on nollamatriisi .

Ominaisuudet

Spektri

Ohjaamattoman yksinkertaisen kuvaajan vierekkäismatriisi on symmetrinen , ja siksi sillä on täydellinen joukko todellisia ominaisarvoja ja ortogonaalinen ominaisvektoripohja . Kaavion ominaisarvojen joukko on kuvaajan spektri . Ominaisarvoja on tavallista merkitä${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}$

Suurinta ominaisarvoa rajoittaa edellä suurin aste. Tämä voidaan nähdä Perron – Frobenius -lauseen tuloksena , mutta se voidaan todistaa helposti. Olkoon v yksi ominaisvektori, joka liittyy ja x komponenttiin, jossa v: llä on suurin absoluuttinen arvo. Olettamatta yleisyyttä menettämättä oletetaan, että v _x on positiivinen, koska muuten yksinkertaisesti otat ominaisvektorin , joka liittyy myös . Sitten ${\ displaystyle \ lambda _ {1}}$${\ displaystyle \ lambda _ {1}}$${\ displaystyle -v}$${\ displaystyle \ lambda _ {1}}$

${\ displaystyle \ lambda _ {1} v_ {x} = (Av) _ {x} = \ summa _ {y = 1}^{n} A_ {x, y} v_ {y} \ leq \ sum _ { y = 1}^{n} A_ {x, y} v_ {x} = v_ {x} \ deg (x).}$

Ja d -regular kaavioita, d on ensimmäinen ominaisarvo vektorin v = (1, ..., 1) (se on helppo tarkistaa, että se on ominaisarvo ja se on suurin, koska edellä sidottu). Tämän ominaisarvon moninaisuus on G: n kytkettyjen komponenttien määrä , erityisesti yhdistettyjen kaavioiden osalta. Voidaan osoittaa, että jokaisen ominaisarvon vastakohta on myös ominaisarvo A, jos G on kaksipuolinen kuvaaja . Erityisesti - d on kahden osapuolen kuvaajan ominaisarvo. ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}}$${\ displaystyle \ lambda _ {i}}$${\ displaystyle -\ lambda _ {i} = \ lambda _ {n+1 -i}}$

Ero on nimeltään spektrin aukko ja se liittyy laajentamiseen ja G . On myös hyödyllistä ottaa käyttöön spektrisäde, joka on merkitty symbolilla . Tätä numeroa rajoittaa . Tämä raja on tiukka Ramanujanin kaavioissa , joilla on sovelluksia monilla alueilla. ${\ displaystyle \ lambda _ {1}-\ lambda _ {2}}$${\ displaystyle A}$${\ displaystyle \ lambda (G) = \ max _ {\ vasen | \ lambda _ {i} \ oikea | <d} | \ lambda _ {i} |}$${\ displaystyle \ lambda (G) \ geq 2 {\ sqrt {d-1}}-o (1)}$

Isomorfismi ja invariantit

Oletetaan, että annetaan kaksi suunnattua tai suunnatonta kuvaajaa G ₁ ja G _2, joilla on vierekkäiset matriisit A ₁ ja A ₂ . G ₁ ja G ₂ ovat isomorfisia silloin ja vain, jos on olemassa sellainen permutaatiomatriisi P , että

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

Erityisesti, ₁ ja ₂ ovat samanlaiset , ja näin ollen on sama minimaalinen polynomi , tunnusomainen polynomi , ominaisarvot , tekijä ja jäljittää . Nämä voivat siksi toimia kaavioiden isomorfismivariaaneina. Kahdella kuvaajalla voi kuitenkin olla sama ominaisarvojoukko, mutta ne eivät voi olla isomorfisia. Tällaisten lineaaristen operaattoreiden sanotaan olevan isospektrisiä .

Matriisin voimat

Jos on vierusmatriisi suunnatun tai suuntaamattoman graafin G , sitten matriisi ⁿ (eli matriisi tuote on n kappaletta ) on mielenkiintoinen tulkinta: elementti ( i , j ) on se määrä (suunnattu tai suunnattomat) kävelee pituudeltaan n kärjestä i pisteeseen j . Jos n on pienin positiivinen kokonaisluku, siten, että joidenkin i , j , elementti ( i , j ) on ⁿ on positiivinen, niin n on etäisyys kärkipisteen i ja solmuun j . Tämä merkitsee sitä, että esimerkiksi määrä kolmioita suuntaamattoman graafin G on täsmälleen jälki on ³ jaettuna 6. vierusmatriisi voidaan käyttää määrittämään, onko vai ei kuvaaja on kytketty .

Tietorakenteet

Vierekkäisyysmatriisia voidaan käyttää tietorakenteena kuvaajan esittämiseen tietokoneohjelmissa, jotka käsittävät kaavioita. Tärkein vaihtoehtoinen tietorakenne, jota käytetään myös tässä sovelluksessa, on vierekkäisyysluettelo .

Koska jokainen vierekkäismatriisin merkintä vaatii vain yhden bitin, se voidaan esittää erittäin kompaktilla tavalla, ja se vie vain | V | ² /8 tavua edustamaan suunnattua kuvaajaa, tai (käyttämällä pakattua kolmion muotoa ja tallentamalla vain matriisin alempi kolmion osa) suunnilleen | V | ² /16 tavua edustamaan suuntaamattoman graafin. Vaikka hieman ytimekkäämpiä esityksiä on mahdollista, tämä menetelmä lähestyy tietoteoreettista alarajaa kaikkien b -bittien vähimmäismäärälle, joka tarvitaan kaikkien n -pisteiden kuvaajan esittämiseen. Kaavioiden tallentamiseen tekstitiedostoihin voidaan käyttää vähemmän bittejä tavua kohti, jotta voidaan varmistaa, että kaikki tavut ovat tekstimerkkejä, esimerkiksi käyttämällä Base64 -esitystä . Sen lisäksi, että vältetään hukkaan menevää tilaa, tämä kompaktius kannustaa paikkaan viitata . Suuren harvakaavion yhteydessä vierekkäiset luettelot vaativat kuitenkin vähemmän tallennustilaa, koska ne eivät tuhlaa tilaa edustamaan reunoja, joita ei ole .

Vaihtoehtoinen vierekkäisyysmatriisin muoto (joka kuitenkin vaatii enemmän tilaa) korvaa matriisin jokaisen elementin numerot reuna -objektien osoittimilla (kun reunat ovat läsnä) tai nollaosoittimilla (kun reunaa ei ole). On myös mahdollista tallentaa reuna painot suoraan osia vierusmatriisiksi.

Avaruuskompromissin lisäksi erilaiset tietorakenteet helpottavat myös eri toimintoja. Kaikkien pisteiden löytäminen tietyn kärjen vierestä vierekkäisluettelossa on yhtä helppoa kuin luettelon lukeminen ja vie aikaa suhteessa naapureiden määrään. Vierekkäismatriisin avulla koko rivi on skannattava, mikä vie enemmän aikaa suhteessa koko kaavion pisteiden määrään. Toisaalta sen testaaminen, onko kahden annetun kärkipisteen välissä reuna, voidaan määrittää kerralla vierekkäismatriisin avulla samalla, kun vaaditaan aikaa, joka on verrannollinen kahden vierekkäisluettelon kärkipisteen vähimmäisasteeseen.

Katso myös

• Laplacian matriisi
• Itse-samankaltaisuusmatriisi

Viitteet

Ulkoiset linkit

• Weisstein, Eric W. "Viereisyysmatriisi" . MathWorld .
• Fluffschack - opettava Java -aloituspeli, joka osoittaa vierekkäisten matriisien ja kaavioiden välisen suhteen.
• Avoimet datarakenteet - Osa 12.1 - Viereisyysmatriisi: Kaavion esittäminen matriisin avulla , Pat Morin
• Kahvila -matematiikka: Kaavioiden  vierekkäiset matriisit : Vierekkäisten matriisien soveltaminen laskennan tuottaviin kävelysarjoihin .