Adjacency matris - Adjacency matrix

Inom grafteori och datavetenskap är en adjacensmatris en kvadratisk matris som används för att representera ett ändligt diagram . Elementen i matrisen indikerar om par av hörn ligger intill eller inte i grafen.

I specialfallet med en begränsad enkel graf är adjacensmatrisen en (0,1) -matris med nollor på sin diagonal. Om grafen inte är riktad (dvs alla dess kanter är dubbelriktade) är adjacensmatrisen symmetrisk . Förhållandet mellan en graf och egenvärden och egenvektorer i dess adjacensmatris studeras i spektralgrafteori .

Adapensmatrisen i en graf bör skiljas från dess incidensmatris , en annan matrisrepresentation vars element indikerar huruvida vertex -edge -par är infallande eller inte, och dess gradmatris , som innehåller information om graden av varje vertex.

Definition

För en enkel graf med toppunktsuppsättning $U = {u 1,\dots, u n$ } är adjacensmatrisen en kvadratisk $n \times n$ matris $A$ så att dess element $A ij$ är en när det finns en kant från toppunkt $u i$ till toppunkt $u j$ och noll när det inte finns någon kant. Matrisens diagonala element är alla noll, eftersom kanter från en toppunkt till sig själv ( slingor ) inte är tillåtna i enkla grafer. Det är också ibland användbart inom algebraisk grafteori att ersätta elementen utan noll mot algebraiska variabler. Samma koncept kan utökas till multigraf och grafer med slingor genom att lagra antalet kanter mellan varje två hörn i motsvarande matriselement och genom att tillåta diagonala element utan noll. Slingor kan räknas antingen en gång (som en enda kant) eller två gånger (som två hörnkantshändelser), så länge en konsekvent konvention följs. Odirigerade grafer använder ofta den senare konventionen att räkna slingor två gånger, medan riktade grafer vanligtvis använder den tidigare konventionen.

Av en tvåpartig graf

Anpassningsmatrisen $A$ för en tvåpartig graf vars två delar har $r$ och $s$ hörn kan skrivas i formen

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

där $B$ är en $r \times s$ -matris, och $0 r, r$ och $0 s, s$ representerar $r \times r$ och $s \times s$ nollmatriser. I det här fallet representerar den mindre matrisen $B$ unikt grafen, och de återstående delarna av $A$ kan kasseras som redundanta. $B$ kallas ibland biadjacensmatrisen .

Formellt, låt $G = (U, V, E)$ vara en tvådelad graf med delar $U = {u 1, ..., u r$ }, $V = {v 1, ..., v s$ } och kanterna $E$ . Den biadjacency matrisen är den $r \times s$ 0-1 matris $B$ , i vilken $b i, j = 1$ om och endast om $(u i, v j) \in E$ .

Om $G$ är en tvåpartig multigraf eller vägd graf , så anses elementen $b i, j$ vara antalet kanter mellan hörnen respektive kantens vikt $(u i, v j)$ .

Variationer

En $(a, b, c)$ -adjacensmatris $A$ i en enkel graf har $A i, j = a$ om $(i, j)$ är en kant, $b$ om den inte är det, och $c$ på diagonalen. Den Seidel grannmatris är en $(-1, 1, 0)$ -adjacency matris. Denna matris används för att studera starkt vanliga grafer och tvågrafer .

Det avstånd matrisen har i position $(i, j)$ är avståndet mellan hörnen $v i$ och $v j$ . Avståndet är längden på den kortaste vägen som förbinder hörnen. Om inte längder på kanter uttryckligen anges är längden på en väg antalet kanter i den. Avståndsmatrisen liknar en hög effekt hos adjacensmatrisen, men istället för att bara berätta om två hörn är anslutna eller inte (det vill säga anslutningsmatrisen, som innehåller booleska värden ), ger det det exakta avståndet mellan dem.

Exempel

Odirigerade grafer

Konventionen som följs här (för oriktade grafer) är att varje kant lägger till 1 till lämplig cell i matrisen, och varje slinga lägger till 2. Detta gör att graden av en toppunkt lätt kan hittas genom att ta summan av värdena i antingen dess respektive rad eller kolumn i angränsningsmatrisen.

Märkt diagram	Adjacency matris
	$$$ Koordinaterna är 1–6.
Nauru -graf	Koordinaterna är 0–23. Vita fält är nollor, färgade fält är ettor.

Riktade grafer

Adacensmatrisen för en riktad graf kan vara asymmetrisk. Man kan definiera adjacensmatrisen för en riktad graf antingen så att

ett icke-noll element $A ij$ indikerar en kant från $i$ till $j$ eller
det indikerar en kant från $j$ till $i$ .

Den tidigare definitionen används vanligen inom grafteori och analys av sociala nätverk (t.ex. sociologi, statsvetenskap, ekonomi, psykologi). Det senare är vanligare inom andra tillämpade vetenskaper (t.ex. dynamiska system, fysik, nätverksvetenskap) där $A$ ibland används för att beskriva linjär dynamik på grafer.

Med hjälp av den första definitionen kan in-graderna för en hörn beräknas genom att summera posterna i motsvarande kolumn och yttergradens hörn genom att summera posterna i motsvarande rad. Vid användning av den andra definitionen ges en hörns in-grad med motsvarande radsumma och ut-graden ges med motsvarande kolumnsumma.

Märkt diagram	Adjacency matris
Riktade Cayley -grafen över S ₄	Koordinaterna är 0–23. Som grafen är riktad är matrisen inte nödvändigtvis symmetrisk .

Triviala grafer

Adacensmatrisen för ett komplett diagram innehåller alla utom längs diagonalen där det bara finns nollor. Adacensmatrisen för en tom graf är en nollmatris .

Egenskaper

Spektrum

Adacensmatrisen för en oriktad enkel graf är symmetrisk och har därför en komplett uppsättning verkliga egenvärden och en ortogonal egenvektorbas . Uppsättningen av egenvärden för en graf är grafens spektrum . Det är vanligt att beteckna egenvärdena med ${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}.}$

Det största egenvärdet begränsas ovan av maxgraden. Detta kan ses som ett resultat av Perron – Frobenius -satsen , men det kan bevisas enkelt. Låt $v$ vara en egenvektor associerad till och $x$ komponenten där $v$ har maximalt absolutvärde. Utan förlust av generalitet antar $v$ $x$ är positivt eftersom du annars tar egenvektorn , också associerad med . Sedan ${\ displaystyle \ lambda _ {1}}$ ${\ displaystyle \ lambda _ {1}}$ ${\ displaystyle -v}$ ${\ displaystyle \ lambda _ {1}}$

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

För $d$ -regelbundna grafer är $d$ det första egenvärdet för $A$ för vektorn $v = (1,\dots, 1)$ (det är lätt att kontrollera att det är ett egenvärde och det är maxvärdet på grund av ovanstående gräns). Mångfaldet av detta egenvärde är antalet anslutna komponenter i $G$ , särskilt för anslutna grafer. Det kan visas att för varje egenvärde är dess motsats också ett egenvärde på $A$ om $G$ är en tvåpartig graf . I synnerhet - $d$ är ett egenvärde för bipartitgrafer. ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}}$ ${\ displaystyle \ lambda _ {i}}$ ${\ displaystyle -\ lambda _ {i} = \ lambda _ {n+1 -i}}$

Skillnaden kallas spektral gapet och det är relaterat till expansionen av $G$ . Det är också användbart för att införa den spektrala radie av betecknad med . Detta nummer begränsas av . Denna gräns är tät i Ramanujan -graferna , som har applikationer inom många områden. ${\ displaystyle \ lambda _ {1}-\ lambda _ {2}}$ ${\ displaystyle A}$ ${\ displaystyle \ lambda (G) = \ max _ {\ left | \ lambda _ {i} \ right | <d} | \ lambda _ {i} |}$ ${\ displaystyle \ lambda (G) \ geq 2 {\ sqrt {d-1}}-o (1)}$

Isomorfism och invarianter

Antag att två riktade eller oriktade grafer $G 1$ och $G 2$ med närliggande matriser $A 1$ och $A 2$ ges. $G 1$ och $G 2$ är isomorfa om och endast om det finns en permutationsmatris $P$ sådan att

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

I synnerhet, $A 1$ och $A 2$ är liknande och därför har samma minimala polynom , karakteristiska polynomet , egenvärden , determinanten och spår . Dessa kan därför fungera som isomorfism invarianter av grafer. Två grafer kan dock ha samma uppsättning egenvärden men inte vara isomorfa. Sådana linjära operatörer sägs vara isospektrala .

Matriskrafter

Om $A$ är adjacensmatrisen för den riktade eller ostyrda grafen $G$ , har matrisen $A n$ (dvs matrisprodukten av $n$ kopior av $A$ ) en intressant tolkning: elementet $(i, j)$ ger antalet (riktade eller icke riktad) promenader med längd $n$ från vertex $i$ till vertex $j$ . Om $n$ är det minsta icke -negativa heltalet, så att för vissa $i$ , $j$ är elementet $(i, j)$ i $A n$ positivt, då är $n$ avståndet mellan toppunkt $i$ och toppunkt $j$ . Detta innebär, till exempel, att antalet trianglar i en oriktad graf $G$ är exakt spår av $A 3$ dividerat med 6. grannmatris kan användas för att bestämma huruvida eller inte grafen ansluten .

Data struktur

Anpassningsmatrisen kan användas som en datastruktur för framställning av grafer i datorprogram för manipulering av grafer. Huvudalternativet datastruktur, används också för detta ändamål, är närhet listan .

Eftersom varje post i adjacensmatrisen bara kräver en bit, kan den representeras på ett mycket kompakt sätt, som bara upptar $| V | 2 /8$ byte för att representera en riktad graf, eller (genom att använda ett packat triangulärt format och bara lagra den nedre triangulära delen av matrisen) ungefär $| V | 2 /16$ byte för att representera en oriktad graf. Även om lite mer kortfattade representationer är möjliga, kommer denna metod nära den informationsteoretiska nedre gränsen för det minsta antal bitar som behövs för att representera alla $n$ -vertexgrafer. För att lagra grafer i textfiler kan färre bitar per byte användas för att säkerställa att alla byte är texttecken, till exempel genom att använda en Base64 -representation . Förutom att undvika slöseri med utrymme, uppmuntrar denna kompakthet till referensplats . För en stor gles graf kräver dock anslutningslistor mindre lagringsutrymme, eftersom de inte slösar bort något utrymme för att representera kanter som inte finns.

En alternativ form av adjacensmatris (som dock kräver större utrymme) ersätter siffrorna i varje element i matrisen med pekare till kantobjekt (när kanter finns) eller nollpekare (när det inte finns någon kant). Det är också möjligt att lagra kantvikter direkt i elementen i en angränsningsmatris.

Förutom rymdavvägningen underlättar de olika datastrukturerna också olika operationer. Att hitta alla hörn intill en viss hörnpunkt i en angränsningslista är lika enkelt som att läsa listan och tar tid som är proportionellt mot antalet grannar. Med en adjacensmatris måste en hel rad istället skannas, vilket tar en längre tid, proportionellt mot antalet hörn i hela grafen. Å andra sidan kan man testa om det finns en kant mellan två givna hörn på en gång med en angränsningsmatris, samtidigt som det kräver tid som är proportionell mot minimigraden för de två hörnen med angränsningslistan.

Se även

Referenser

externa länkar

Weisstein, Eric W. "Adjacency matrix" . MathWorld .
Fluffschack - ett pedagogiskt Java -webbspel som visar sambandet mellan närliggande matriser och grafer.
Öppna datastrukturer - Avsnitt 12.1 - AdjacencyMatrix: Representation a Graph by a Matrix , Pat Morin
Kafématematik: Adjacency Matrices of Graphs : Tillämpning av adjacensmatriserna på beräkningen som genererar serier av promenader.

Languages

In other projects