Adjacency matrix

En tilstødende matrix er en måde at repræsentere en graf som en matrix.

Definition

Tilstødende matrix af en graf med et endeligt antal hjørner (nummereret fra 1 til ) er en kvadratisk heltalsmatrix af størrelse , hvor elementværdien er lig med antallet af kanter fra det th toppunkt af grafen til det th toppunkt. $G$ $n$ $n$ ${\mathbf A}$ $n\ gange n$ $a_{i,j}$ $jeg$ $j$

Nogle gange, især i tilfælde af en urettet graf, tæller en sløjfe (en kant fra det -. vertex til sig selv) som to kanter, det vil sige, at værdien af det diagonale element i dette tilfælde er lig med det dobbelte af antallet af sløjfer omkring det -te toppunkt. $jeg$ ${\displaystyle a_{i,i))$ $jeg$

Den tilstødende matrix af en simpel graf (der ikke indeholder sløjfer eller flere kanter) er en binær matrix og indeholder nuller på hoveddiagonalen .

Adjacency-matrixen af en todelt graf

Adjacency-matrixen af en todelt graf , hvis dele også har toppunkter , kan skrives på følgende form ${\mathbf A}$ $r$ $s$

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

hvor er en matrix, og og er nul - matricer. I dette tilfælde repræsenterer den mindre matrix entydigt grafen, og de resterende dele af matrixen kan kasseres. undertiden kaldet bis-adjacency-matrixen. $\mathbf {B}$ $r\times s$ ${\displaystyle \mathbf {0} _{r,r))$ $\mathbf {0} _{s,s}$ $r\times r$ $s\ gange s$ $\mathbf {B}$ ${\mathbf A}$ $\mathbf {B}$

Formelt, lad være en todelt graf med dele og . En bikonjugeret matrix er en 0-1 matrix , hvor hvis og kun hvis . $G=(U,V,E)$ $U=\{u_{1},\dots ,u_{r}\}$ $V=\{v_{1},\dots ,v_{s}\}$ $r\times s$ $\mathbf {B}$ $b_{i,j}=1$ $(u_{i},v_{j})\in E$

Hvis er en todelt multigraf eller en vægtet graf, så vil elementerne være henholdsvis antallet af kanter mellem hjørner eller vægten af kanterne . $G$ ${\displaystyle b_{i,j))$ $(u_{i},v_{j})$

Eksempler

Nedenfor er et eksempel på en urettet graf og dens tilsvarende tilstødende matrix . Denne graf indeholder en løkke omkring toppunkt 1, og afhængigt af specifikke anvendelser kan et element betragtes som lig med enten en (som vist nedenfor) eller to. ${\mathbf A}$ $a_{1,1}$

Kurve	Adjacency matrix
	${\displaystyle {\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))$

$a_{i,j}$ er antallet af kanter, der forbinder hjørnerne og , og i nogle applikationer tælles hver sløjfe (kant for nogle ) to gange. $v_{i}$ $v_{j}$ $\{v_{i},v_{i}\}$ $jeg$

Tilstødende matrix af en tom graf, der ikke indeholder kanter, består af alle nuller.

Egenskaber

Adjacency-matrixen af en urettet graf er symmetrisk , hvilket betyder, at den har reelle egenværdier og en ortogonal basis af egenvektorer. Sættet af dets egenværdier kaldes grafens spektrum og er hovedemnet for undersøgelse i spektralgrafteori .

To grafer og med tilstødende matricer og er isomorfe , hvis og kun hvis der eksisterer en permutationsmatrix, således at $G_{1}$ $G_{2}$ $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$

{\displaystyle \mathbf {P} \mathbf {A} _{1}\mathbf {P} ^{-1}=\mathbf {A} _{2))

Det følger af dette, at matricerne og er ens , og derfor har lige store sæt af egenværdier, determinanter og karakteristiske polynomier. Det modsatte er dog ikke altid sandt - to grafer med lignende tilstødende matricer er muligvis ikke isomorfe (dette sker, hvis matrixen ikke er permuterbar, f.eks. matricerne og ligner hinanden, men de tilsvarende grafer er ikke isomorfe). $\mathbf {A} _{1}$ ${\displaystyle \mathbf {A} _{2))$ $\mathbf {P}$ ${\begin{pmatrix}0&1\\0&0\end{pmatrix}}$ ${\begin{pmatrix}0&2\\0&0\end{pmatrix}}$

Matrix kræfter

Hvis er grafens tilstødende matrix , så har matrixen følgende egenskab: elementet i -th række, -th kolonne er lig med antallet af stier fra -th toppunkt til -th, bestående af nøjagtigt kanter. ${\mathbf A}$ $G$ $\mathbf {A} ^{m}$ $jeg$ $j$ $jeg$ $j$ $m$

Datastruktur

Adjacency matrix og adjacency lister er de vigtigste datastrukturer , der bruges til at repræsentere grafer i computerprogrammer.

Brug af en tilstødende matrix er kun at foretrække i tilfælde af ikke-sparsomme grafer med et stort antal kanter, da det kræver lagring af en bit data for hvert element. Hvis grafen er sparsom, vil det meste af hukommelsen blive spildt på at gemme nuller, men i tilfælde af ikke-sparsomme grafer repræsenterer tilstødende matrix grafen i hukommelsen ret kompakt, idet den bruger omkring en smule hukommelse, hvilket kan være en rækkefølge af størrelsesorden bedre end tilgrænsende lister. $n^{2}$

I algoritmer, der arbejder med vægtede grafer (f.eks. i Floyd-Warshall-algoritmen ), indeholder elementerne i tilstødende matrix, i stedet for tallene 0 og 1, der angiver tilstedeværelsen eller fraværet af en kant, ofte vægten af kanterne dem selv. Samtidig sættes en speciel grænseværdi ( engelsk sentinel ) i stedet for de manglende kanter , afhængigt af problemet, der løses, normalt 0 eller . $\infty$

Se også

Litteratur

Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Ed. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .