Adjazenzmatrix

Im Graphentheorie und Informatik, ein Adjazenzmatrix ist ein quadratische Matrix Wird verwendet, um eine endliche darzustellen Graph. Die Elemente der Matrix angeben, ob Paare von Eckpunkte sind benachbart oder nicht in der Grafik.

Im Sonderfall einer endlichen Einfaches DiagrammDie Adjazenzmatrix ist a (0,1) -matrix mit Nullen auf der Diagonale. Wenn die Grafik ist ungerichtet (d. H. Alle seine Kanten sind bidirektional), die Adjazenzmatrix ist symmetrisch. Die Beziehung zwischen einer Grafik und der Eigenwerte und Eigenvektoren seiner Adjazenzmatrix wird in untersucht Spektralgraphentheorie.

Die Adjazenzmatrix eines Diagramms sollte von seiner unterschieden werden Inzidenzmatrix, eine andere Matrixdarstellung, deren Elemente angeben, ob sich die Vertex -Edge -Paare befinden Vorfall oder nicht und seine Gradmatrix, was Informationen über die enthält Grad von jedem Scheitelpunkt.

Definition

Für ein einfaches Diagramm mit Scheitelpunkt -Set $U = {{u 1,\dots, u n$ } Die Adjazenzmatrix ist ein Quadrat $n \times n$ Matrix $A$ so dass sein Element $A ij$ ist einer, wenn es eine Kante von Scheitelpunkt gibt $u i$ zu Scheitelpunkt $u j$ und Null, wenn es keine Kante gibt.^[1] Die diagonalen Elemente der Matrix sind alle Null, da Kanten von einem Scheitelpunkt zu sich selbst (Schleifen) sind in einfachen Grafiken nicht erlaubt. Es ist auch manchmal nützlich in Algebraische Graphentheorie Ersetzen Sie die Elemente ungleich Null durch algebraische Variablen.^[2] Das gleiche Konzept kann erweitert werden auf Multigraphen und Diagramme mit Schleifen durch Speichern der Anzahl der Kanten zwischen den beiden Scheitelpunkten im entsprechenden Matrixelement und durch Erlaubnis von diagonalen Elementen ungleich Null. Schleifen können entweder einmal (als einzelne Kante) oder zweimal (als zwei Ereignisse der Scheitelpunktkanten) gezählt werden, solange ein konsistenter Konvention befolgt wird. Unbekannte Diagramme verwenden häufig die letztere Konvention von Zählschleifen zweimal, während gerichtete Graphen normalerweise die erstere Konvention verwenden.

Einer zweigliedrigen Grafik

Die Adjazenzmatrix $A$ von a Bipartitale Grafik deren zwei Teile haben $r$ und $s$ Scheitelpunkte können in der Form geschrieben werden

oder

wo $B$ ist ein $r \times s$ Matrix und $0 r, r$ und $0 s, s$ repräsentieren $r \times r$ und $s \times s$ Null Matrizen. In diesem Fall die kleinere Matrix $B$ repräsentiert eindeutig die Grafik und die verbleibenden Teile von $A$ kann als überflüssig verworfen werden. $B$ wird manchmal das genannt BiadjaCacy -Matrix.

Formal, lassen Sie $G = (U, V, E)$ sei a Bipartitale Grafik mit Teilen $U = {{u 1,\dots, u r$ }, $V = {{v 1,\dots, v s$ } und Kanten $E$ . Die Biadjazenzmatrix ist die $r \times s$ 0–1 Matrix $B$ in welchem $b i, j = 1$ dann und nur dann, wenn $(u i, v j) \in E$ .

Wenn $G$ ist ein zweipartneres Multigraph oder gewichtete Grafikdann die Elemente $b Ich, j$ werden als die Anzahl der Kanten zwischen den Eckpunkten oder dem Gewicht der Kante angesehen $(u i, v j)$ , beziehungsweise.

Variationen

Ein $(a, b, c)$ -Adjazenzmatrix $A$ einer einfachen Grafik hat $A i, j = a$ wenn $(i, j)$ ist eine Kante, $b$ Wenn nicht, und $c$ auf der Diagonale. Das Seidel -Adjazenzmatrix ist ein $(-1, 1, 0)$ -Adjazenzmatrix. Diese Matrix wird beim Studium verwendet stark reguläre Grafiken und Zwei-Graphen.^[3]

Das Entfernungsmatrix hat in Position $(i, j)$ der Abstand zwischen Scheitelpunkten $v i$ und $v j$ . Der Abstand ist die Länge eines kürzesten Pfades, der die Eckpunkte verbindet. Sofern die Kantenlängen explizit bereitgestellt werden, beträgt die Länge eines Pfades die Anzahl der Kanten darin. Die Entfernungsmatrix ähnelt einer hohen Leistung der Adjazenzmatrix, aber anstatt nur zu sagen, ob zwei Scheitelpunkte verbunden sind oder nicht (d. H. Die Verbindungsmatrix, die enthält boolesche Werte), es gibt den genauen Abstand zwischen ihnen.

Beispiele

Ungerichtete Grafiken

Die hier folgende Konvention (für ungerichtete Graphen) ist, dass jede Kante 1 zur entsprechenden Zelle in der Matrix hinzufügt und jede Schleife 2 hinzugefügt wird.^[4] Dadurch kann der Grad eines Scheitelpunkts leicht gefunden werden, indem die Summe der Werte entweder in seiner jeweiligen Zeile oder in der Spalte in der Adjazenzmatrix eingenommen wird.

Beschriftete Grafik	Adjazenzmatrix
	${\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}}$ Die Koordinaten sind 1–6.
Nauru Graph	Die Koordinaten sind 0–23. Weiße Felder sind Nullen, farbige Felder sind diejenigen.

Regie Graphen

Die Adjazenzmatrix eines gerichteten Diagramms kann asymmetrisch sein. Man kann die Adjazenzmatrix eines gerichteten Diagramms entweder so definieren, dass

ein Element ungleich Null $A ij$ zeigt eine Kante von an $i$ zu $j$ oder
es zeigt eine Kante von an $j$ zu $i$ .

Die erstere Definition wird häufig in der Graphentheorie und der Analyse des sozialen Netzwerks (z. B. Soziologie, Politikwissenschaft, Wirtschaft, Psychologie) verwendet.^[5] Letzteres ist häufiger in anderen angewandten Wissenschaften (z. B. dynamische Systeme, Physik, Netzwerkwissenschaft), wo $A$ wird manchmal verwendet, um die lineare Dynamik in Grafiken zu beschreiben.^[6]

Verwenden der ersten Definition die In-Teger eines Scheitelpunkts kann berechnet werden, indem die Einträge der entsprechenden Spalte und der Außenabschluss des Scheitelpunkts summiert werden, indem die Einträge der entsprechenden Zeile summiert werden. Bei Verwendung der zweiten Definition wird der In-Grad eines Scheitelpunkts durch die entsprechende Zeilensumme angegeben, und der Außenabschluss wird durch die entsprechende Spaltensumme gegeben.

Beschriftete Grafik	Adjazenzmatrix
Gerichtet Cayley -Graph von S₄	Die Koordinaten sind 0–23. Wie die Grafik gerichtet ist, ist die Matrix nicht unbedingt symmetrisch.

Triviale Graphen

Die Adjazenzmatrix von a Komplette Graph Enthält alle, außer entlang der Diagonale, wo es nur Nullen gibt. Die Adjazenzmatrix von a leere Grafik ist ein Null Matrix.

Eigenschaften

Spektrum

Die Adjazenzmatrix eines ungerichteten einfachen Diagramms ist symmetrischund hat daher einen vollständigen Satz von real Eigenwerte und eine orthogonale Eigenvektor Basis. Der Satz der Eigenwerte einer Grafik ist die Spektrum der Grafik.^[7] Es ist üblich, die Eigenwerte zu bezeichnen $oder$

Der größte Eigenwert ${\ displayStyle \ lambda _ {1}}$ wird oben nach maximalem Grad begrenzt. Dies kann als Ergebnis der gesehen werden Perron -Frobenius -Theorem, aber es kann leicht bewiesen werden. Lassen $v$ ein Eigenvektor sein, der mit dem verbunden ist ${\ displayStyle \ lambda _ {1}}$ und $x$ die Komponente, in der $v$ hat einen maximalen absoluten Wert. Ohne Verlust der Allgemeinheit angenommen $v x$ ist positiv, da Sie sonst einfach den Eigenvektor nehmen ${\ displayStyle -v}$ ebenfalls verbunden mit ${\ displayStyle \ lambda _ {1}}$ . Dann

oder y = 1}^{n} a_ {x, y} v_ {x} = v_ {x} \ deg (x).}

Zum $d$ -reguläre Graphen, $d$ ist der erste Eigenwert von $A$ Für den Vektor $v = (1,\dots, 1)$ (Es ist leicht zu überprüfen, ob es sich um einen Eigenwert handelt und der maximal aufgrund der oben genannten Grenze ist.) Die Multiplizität dieses Eigenwerts ist die Anzahl der verbundenen Komponenten von $G$ , im Speziellen ${\ displaystyle \ lambda _ {1}> \ lambda _ {2}}$ Für angeschlossene Graphen. Es kann gezeigt werden, dass für jeden Eigenwert ${\ displaystyle \ lambda _ {i}}$ , sein Gegenteil ${\ displayStyle -\ lambda _ {i} = \ lambda _ {n+1 -i}}$ ist auch ein Eigenwert von $A$ wenn $G$ ist ein Bipartitale Grafik.^[8] Insbesondere - $d$ ist ein Eigenwert von jedem $d$ -reguläres zweipartneres Diagramm.

Der Unterschied ${\ displaystyle \ lambda _ {1}-\ lambda _ {2}}$ wird genannt Spektrallücke und es hängt mit dem zusammen Erweiterung von $G$ . Es ist auch nützlich, die vorzustellen Spektralradius von ${\ displayStyle a}$ bezeichnet durch $oder$ . Diese Zahl wird von begrenzt ${\ displayStyle \ lambda (g) \ Geq 2 {\ sqrt {d-1}}-o (1)}$ . Diese Grenze ist eng in der Ramanujan -Grafiken, die Anwendungen in vielen Bereichen haben.

Isomorphismus und Invarianten

Nehmen Sie zwei gerichtete oder ungerichtete Graphen an $G 1$ und $G 2$ mit Adjazenzmatrizen $A 1$ und $A 2$ sind gegeben. $G 1$ und $G 2$ sind isomorph Wenn und nur wenn es vorhanden ist a Permutationsmatrix $P$ so dass

{\ displayStyle pa_ {1} p^{-1} = a_ {2}.}

Im Speziellen, $A 1$ und $A 2$ sind ähnlich und haben daher das gleiche Minimales Polynom, charakteristisches Polynom, Eigenwerte, bestimmend und verfolgen. Diese können daher als Isomorphismus -Invarianten von Graphen dienen. Zwei Grafiken können jedoch den gleichen Satz von Eigenwerten besitzen, aber nicht isomorph.^[9] Eine solche lineare Operatoren sollen sein Isspectral.

Matrixmächte

Wenn $A$ ist die Adjazenzmatrix des gerichteten oder ungerichteten Graphen $G$ dann die Matrix $A n$ (d.h. die Matrixprodukt von $n$ Kopien von $A$ ) hat eine interessante Interpretation: das Element $(i, j)$ gibt die Anzahl der (gerichteten oder ungerichteten) Spaziergänge von Länge $n$ von Scheitelpunkt $i$ zu Scheitelpunkt $j$ . Wenn $n$ ist die kleinste nichtnegative Ganzzahl, so dass für einige $i$ , $j$ , das Element $(i, j)$ von $A n$ ist dann positiv $n$ ist der Abstand zwischen Scheitelpunkt $i$ und Scheitelpunkt $j$ . Dies impliziert zum Beispiel, dass die Anzahl der Dreiecke in einer ungerichteten Grafik $G$ ist genau das verfolgen von $A 3$ geteilt durch 6. Die Adjazenzmatrix kann verwendet werden, um festzustellen, ob der Diagramm ist oder nicht in Verbindung gebracht.

Datenstrukturen

Die Adjazenzmatrix kann als verwendet werden Datenstruktur für die Darstellung von Graphen in Computerprogrammen zum Manipulieren von Graphen. Die wichtigste alternative Datenstruktur, die ebenfalls für diese Anwendung verwendet wird, ist die Adjazenzliste.^[10]^[11]

Da jeder Eintrag in der Adjazenzmatrix nur ein Bit erfordert, kann sie sehr kompakt dargestellt werden, die nur |V|²/8 Bytes zur Darstellung eines gerichteten Diagramms oder (unter Verwendung eines gepackten dreieckigen Formats und der Speicherung des unteren dreieckigen Teils der Matrix) ungefähr |V|²/16 Bytes zur Darstellung eines ungerichteten Diagramms. Obwohl etwas prägnantere Darstellungen möglich sind, nähert sich diese Methode der Informations-theoretischen Untergrenze für die minimale Anzahl von Bits, die für alle erforderlich sind, um alle darzustellen $n$ -Vertex -Diagramme.^[12] Zum Speichern von Grafiken in Textdateien, weniger Bits pro Byte können verwendet werden, um sicherzustellen, dass alle Bytes beispielsweise mit a Textzeichen sind Basis64 Darstellung.^[13] Diese Kompaktheit vermeidet nicht nur verschwendete Raum Referenzort. Allerdings für eine große spärliche Grafik, Adjazenzlisten erfordern weniger Speicherplatz, da sie keinen Platz verschwenden, um Kanten darzustellen, die sind nicht gegenwärtig.^[11]^[14]

Eine alternative Form der Adjazenzmatrix (die jedoch eine größere Menge an Platz erfordert) ersetzt die Zahlen in jedem Element der Matrix durch Zeiger auf Kantenobjekte (wenn Kanten vorhanden sind) oder Nullzeiger (wenn es keine Kante gibt).^[14] Es ist auch möglich zu speichern Kantengewichte direkt in den Elementen einer Adjazenzmatrix.^[11]

Neben dem Weltraum -Kompromiss erleichtern die verschiedenen Datenstrukturen auch unterschiedliche Operationen. Das Finden aller Scheitelpunkte neben einem bestimmten Scheitelpunkt in einer Adjazenzliste ist so einfach wie das Lesen der Liste und nimmt Zeit proportional zur Anzahl der Nachbarn. Mit einer Adjazenzmatrix muss stattdessen eine ganze Reihe gescannt werden, was mehr Zeit in Anspruch nimmt, proportional zur Anzahl der Eckpunkte im gesamten Diagramm. Andererseits kann getestet werden, ob eine Kante zwischen zwei gegebenen Scheitelpunkten besteht, kann gleichzeitig mit einer Adjazenzmatrix bestimmt werden, während die Zeit proportional zum Mindestgrad der beiden Scheitelpunkte mit der Adjazenzliste erforderlich ist.^[11]^[14]

Siehe auch

Verweise

^ Biggs, Norman (1993), Algebraische Graphentheorie, Cambridge Mathematical Library (2. Aufl.), Cambridge University Press, Definition 2.1, p. 7.
^ Harary, Frank (1962), "die Determinante der Adjazenzmatrix eines Graphen", Siam Review, 4 (3): 202–210, Bibcode:1962Siamr ... 4..202H, doi:10.1137/1004057, HERR 0144330.
^ Seidel, J. J. (1968). "Starke reguläre Diagramme mit (–1, 1, 0) Adjazenzmatrix mit Eigenwert 3". Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795 (68) 90008-6.
^ Shum, Kenneth; Blake, Ian (2003-12-18). "Expander -Diagramme und -Codes". Band 68 der DIMACS -Serien in diskreter Mathematik und theoretischer Informatik. Algebraische Codierungstheorie und Informationstheorie: DIMACS -Workshop, Algebraik -Codierungstheorie und Informationstheorie. American Mathematical Society. p. 63. ISBN 9780821871102.
^ Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyse sozialer Netzwerke (2. Aufl.), Sage, p. 20
^ Newman, Mark (2018), Netzwerke (2. Aufl.), Oxford University Press, p. 110
^ Biggs (1993), Kapitel 2 ("Das Spektrum eines Diagramms"), S. 7–13.
^ Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartiten Diagramme", Spektren von Graphen, Universitechse, New York: Springer, S. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, HERR 2882891
^ Godsil, Chris; Royle, Gordon Algebraische Graphentheorie, Springer (2001), ISBN0-387-95241-1, S.164
^ Goodrich & Tamassia (2015), p. 361: "Es gibt zwei Datenstrukturen, mit denen Menschen häufig Diagramme darstellen, die Adjazenzliste und die Adjazenzmatrix."
^ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Abschnitt 22.1: Darstellungen von Graphen", Einführung in Algorithmen (Second Ed.), MIT Press und McGraw-Hill, S. 527–531, ISBN 0-262-03293-7.
^ Turán, György (1984), "Über die prägnante Darstellung von Graphen", Diskrete angewandte Mathematik, 8 (3): 289–294, doi:10.1016/0166-218x (84) 90126-4, HERR 0749658.
^ McKay, Brendan, Beschreibung von Graph6- und Sparse6 -Codierungen.
^ ^a ^b ^c Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithmus Design und Anwendungen, Wiley, p.363.

Externe Links

Weisstein, Eric W. "Adjazenzmatrix". Mathord.
Fluffschack - Ein pädagogisches Java -Web -Startspiel, das die Beziehung zwischen Adjazenzmatrizen und Grafiken demonstriert.
Offene Datenstrukturen - Abschnitt 12.1 - Adjazenzmatrix: Darstellung eines Diagramms durch eine Matrix darstellen, Pat Morin
Café Math: Adjazenzmatrizen von Graphen: Anwendung der Adjazenzmatrizen auf die Berechnungserzeugungsreihe von Spaziergängen.

[1] Biggs, Norman (1993), Algebraische Graphentheorie, Cambridge Mathematical Library (2. Aufl.), Cambridge University Press, Definition 2.1, p. 7.

[2] Harary, Frank (1962), "die Determinante der Adjazenzmatrix eines Graphen", Siam Review, 4 (3): 202–210, Bibcode:1962Siamr ... 4..202H, doi:10.1137/1004057, HERR 0144330.

[3] Seidel, J. J. (1968). "Starke reguläre Diagramme mit (–1, 1, 0) Adjazenzmatrix mit Eigenwert 3". Lin. Alg. Appl. 1 (2): 281–298. doi:10.1016/0024-3795 (68) 90008-6.

[4] Shum, Kenneth; Blake, Ian (2003-12-18). "Expander -Diagramme und -Codes". Band 68 der DIMACS -Serien in diskreter Mathematik und theoretischer Informatik. Algebraische Codierungstheorie und Informationstheorie: DIMACS -Workshop, Algebraik -Codierungstheorie und Informationstheorie. American Mathematical Society. p. 63. ISBN 9780821871102.

[5] Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyse sozialer Netzwerke (2. Aufl.), Sage, p. 20

[6] Newman, Mark (2018), Netzwerke (2. Aufl.), Oxford University Press, p. 110

[7] Biggs (1993), Kapitel 2 ("Das Spektrum eines Diagramms"), S. 7–13.

[8] Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartiten Diagramme", Spektren von Graphen, Universitechse, New York: Springer, S. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN 978-1-4614-1938-9, HERR 2882891

[9] Godsil, Chris; Royle, Gordon Algebraische Graphentheorie, Springer (2001), ISBN0-387-95241-1, S.164

[10] Goodrich & Tamassia (2015), p. 361: "Es gibt zwei Datenstrukturen, mit denen Menschen häufig Diagramme darstellen, die Adjazenzliste und die Adjazenzmatrix."

[clrs-11] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Abschnitt 22.1: Darstellungen von Graphen", Einführung in Algorithmen (Second Ed.), MIT Press und McGraw-Hill, S. 527–531, ISBN 0-262-03293-7.

[12] Turán, György (1984), "Über die prägnante Darstellung von Graphen", Diskrete angewandte Mathematik, 8 (3): 289–294, doi:10.1016/0166-218x (84) 90126-4, HERR 0749658.

[13] McKay, Brendan, Beschreibung von Graph6- und Sparse6 -Codierungen.

[gt-14] Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithmus Design und Anwendungen, Wiley, p.363.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

Grafikdarstellungen
Datenstrukturen	Graph (abstrakter Datentyp) Adjazenzliste Kantenliste Adjazenzmatrix Inzidenzmatrix
XML-basierte Formate	DGML Dotml Gexf Graphml GXL Xgmml
Textbasierte Formate	PUNKT Grafikmodellierungssprache (GML) LCF -Notation Für kubische Hamiltonsche Graphen Neues Format für Bäume Triviales Diagrammformat
Verwandte konzepte	Graph database Grafikzeichnung Verknüpfte Daten

Matrix Klassen
Explizit eingeschränkte Einträge	Wechsel Antidiagonal Anti-Hermitian Antisymmetrisch Pfeilspitze Band Bidiagonal Bisymmetrisch Blockdiagonal Block Block Triagonal Boolesche Cauchy Zentrosymmetrie Konferenz Komplexer Hadamard Kopositiv Diagonal dominant Diagonale diskrete Fourier-Transformation Elementar Äquivalent Frobenius Verallgemeinerte Permutation Hadamard Hankel Hermitianer Hessenberg Hohl Ganze Zahl Logisch Matrixeinheit Metzler Moore Nicht negativ Pentadiagonal Permutation Perymmetrisch Polynom Quaternion Unterschrift Schief hermitisch Schief symmetrisch Horizont Spärlich Sylvester Symmetrisch Toeplitz Dreieckig Triagonal Vandermonde Walsh Z
Konstante	Austausch Hilbert Identität Lehm Von eins Pascal Pauli Redheffer Wechsel Null
Bedingungen auf Eigenwerte oder Eigenvektoren	Begleiter Konvergent Defekt Definitiv Diagonalisierbar Hurwitz Positiv-definit Stieltjes
Befriedigende Bedingungen auf Produkte oder Inversen	Kongruent Idempotent oder Projektion Invertierbar Involutorisch Nilpotent Normal Senkrecht Unimodular Unipotent Einheitlich Völlig unimodular Wiegen
Mit spezifischen Anwendungen	Adjugate Wechselzeichen Erweitert Bézout Carleman Cartan Kreislauf Cofaktor Kommutierung Verwirrtheit Koxeter Distanz Duplizierung und Eliminierung Euklidische Entfernung Grundlegend (lineare Differentialgleichung) Generator Gramm Hessian Hausbesitzer Jacobian Moment Auszahlen Wählen Zufällig Drehung Seifert Scheren Ähnlichkeit Sympplektisch Total positiv Transformation
Benutzt in Statistiken	Zentrierung Korrelation Kovarianz Entwurf Doubly stochastic Fischerinformationen Hut Präzision Stochastisch Übergang
Benutzt in Graphentheorie	Adjazenz Biadjazenz Grad Edmonds Vorfall Laplace Seidel -Adjazenz Tutte
Wird in Wissenschaft und Ingenieurwesen verwendet	CABIBBO -KOBAYASHI -MASKAWA Dichte Grundlegend (Computer Vision) Fuzzy assoziativ Gamma Gell-Mann Hamiltonian Irregulär Überlappung S Zustandsübergang Auswechslung Z (Chemie)
Verwandte Begriffe	Jordanische Normalform Lineare Unabhängigkeit Matrix exponentiell Matrixdarstellung von Kegelabschnitten Perfekte Matrix Pseudoinverse Reihen -Echelon -Form Wronskianer
Mathematikportal Liste der Matrizen Kategorie: Matrizen