In der Mathematik und Informatik ist eine Angrenzen-Matrix ein Mittel des Darstellens, das Scheitelpunkte (oder Knoten) eines Graphen neben der andere Scheitelpunkte sind. Eine andere Matrixdarstellung für einen Graphen ist die Vorkommen-Matrix.

Spezifisch ist die Angrenzen-Matrix eines begrenzten Graphen G auf n Scheitelpunkten der n × n Matrix, wo der nichtdiagonale Zugang der Zahl von Rändern vom Scheitelpunkt i zum Scheitelpunkt j und dem diagonalen Zugang a abhängig von der Tagung zu sein, irgendein einmal oder zweimal die Zahl von Rändern (Schleifen) vom Scheitelpunkt i zu sich ist. Ungeleitete Graphen verwenden häufig die letzte Tagung des Zählens von Schleifen zweimal, wohingegen geleitete Graphen normalerweise die ehemalige Tagung verwenden. Dort besteht eine einzigartige Angrenzen-Matrix für jede Isomorphismus-Klasse von Graphen (bis zum Permutieren von Reihen und Säulen), und es ist nicht die Angrenzen-Matrix jeder anderen Isomorphismus-Klasse von Graphen. Im speziellen Fall eines begrenzten einfachen Graphen ist die Angrenzen-Matrix (0,1) - Matrix mit Nullen auf seiner Diagonale. Wenn der Graph ungeleitet ist, ist die Angrenzen-Matrix symmetrisch.

Die Beziehung zwischen einem Graphen und dem eigenvalues und den Eigenvektoren seiner Angrenzen-Matrix wird in der geisterhaften Graph-Theorie studiert.

Beispiele

Die Tagung gefolgt hier besteht darin, dass ein angrenzender Rand 1 in der Matrix für einen ungeleiteten Graphen zählt.

• Die Angrenzen-Matrix eines ganzen Graphen ist alles 1's abgesehen von 0's auf der Diagonale.
• Die Angrenzen-Matrix eines leeren Graphen ist eine Nullmatrix.

Angrenzen-Matrix eines zweiteiligen Graphen

Die Angrenzen-Matrix eines zweiteiligen Graphen, dessen Teile r und s Scheitelpunkte haben, hat die Form

wo B ein r &times ist; s Matrix und O ist eine Vollnullmatrix. Klar vertritt die Matrix B einzigartig die zweiteiligen Graphen. Es wird manchmal die biadjacency Matrix genannt.

Lassen Sie formell G = (U, V, E) ein zweiteiliger Graph mit Teilen sein und. Die biadjacency Matrix ist der r x s 0-1 Matrix B in der iff.

Wenn G ein zweiteiliger Mehrgraph oder beschwerter Graph dann ist, werden die Elemente genommen, um die Zahl von Rändern zwischen den Scheitelpunkten oder dem Gewicht des Randes beziehungsweise zu sein.

Eigenschaften

Die Angrenzen-Matrix eines ungeleiteten einfachen Graphen ist symmetrisch, und hat deshalb einen ganzen Satz von echtem eigenvalues und einer orthogonalen Eigenvektor-Basis. Der Satz von eigenvalues eines Graphen ist das Spektrum des Graphen.

Nehmen Sie zwei geleitete oder ungeleitete Graphen und mit dem Angrenzen matrices an, und werden gegeben. und sind isomorph, wenn, und nur wenn dort eine solche Versetzungsmatrix dass besteht

Insbesondere und sind ähnlich und haben deshalb dasselbe minimale Polynom, charakteristisches Polynom, eigenvalues, Determinante und Spur. Diese können deshalb als Isomorphismus invariants Graphen dienen. Jedoch können zwei Graphen denselben Satz von eigenvalues besitzen, aber nicht isomorph sein.

Wenn A die Angrenzen-Matrix des geleiteten oder ungeleiteten Graphen G ist, dann hat die Matrix (d. h., das Matrixprodukt von n Kopien von A) eine interessante Interpretation: Der Zugang in der Reihe i und Spalte j gibt die Zahl (geleitet oder ungeleitet) Spaziergänge der Länge n vom Scheitelpunkt i zum Scheitelpunkt j. Das deutet zum Beispiel an, dass die Zahl von Dreiecken in einem ungeleiteten Graphen G genau die Spur Eines geteilten durch 6 ist.

Die Hauptdiagonale jeder Angrenzen-Matrix entsprechend einem Graphen ohne Schleifen hat alle Nulleinträge. Bemerken Sie dass hier 'Schleife'-Mittel, zum Beispiel A-> A, nicht 'Zyklen' wie A-> B-> A.

Für - regelmäßige Graphen ist d auch ein eigenvalue für den Vektoren und wird verbunden, wenn, und nur wenn die Vielfältigkeit dessen 1 ist. Es kann gezeigt werden, dass das auch ein eigenvalue ist, wenn G ein verbundener zweiteiliger Graph ist. Der obengenannte ist Ergebnisse des Perron-Frobenius Lehrsatzes.

Schwankungen

(a, b, c) - hat Angrenzen-Matrix eines einfachen Graphen =, wenn ij ein Rand, b ist, wenn es nicht, und c auf der Diagonale ist. Die Seidel Angrenzen-Matrix ist (1,1,0) - Angrenzen-Matrix. Diese Matrix wird im Studieren stark regelmäßiger Graphen und zwei Graphen verwendet.

Die Entfernungsmatrix hat in der Position (ich, j) die Entfernung zwischen Scheitelpunkten v und v. Die Entfernung ist die Länge eines kürzesten Pfads, der die Scheitelpunkte verbindet. Wenn Längen von Rändern nicht ausführlich zur Verfügung gestellt werden, ist die Länge eines Pfads die Zahl von Rändern darin. Die Entfernungsmatrix ähnelt einer hohen Macht der Angrenzen-Matrix, aber anstatt zu erzählen, nur ob zwei Scheitelpunkte verbunden werden (d. h., die Verbindungsmatrix, die Boolean-Werte enthält), gibt es die genaue Entfernung zwischen ihnen.

Datenstrukturen

Für den Gebrauch als eine Datenstruktur ist die Hauptalternative zur Angrenzen-Matrix die Angrenzen-Liste. Weil jeder Zugang in der Angrenzen-Matrix nur ein Bit verlangt, kann es auf eine sehr kompakte Weise vertreten werden, nur Bytes des aneinander grenzenden Raums besetzend, wo die Zahl von Scheitelpunkten ist. Außer dem Vermeiden des vergeudeten Raums fördert diese Kompaktheit Gegend der Verweisung.

Jedoch, wenn der Graph spärlich ist, verlangen Angrenzen-Listen weniger Abstellraum, weil sie keinen Raum vergeuden, um Ränder zu vertreten, die nicht da sind. Mit einer naiven Reihe-Durchführung auf einem 32-Bit-Computer verlangt eine Angrenzen-Liste für einen ungeleiteten Graphen über Bytes der Lagerung, wo die Zahl von Rändern ist.

Bemerkend, dass ein einfacher Graph an den meisten Rändern haben kann, Schleifen erlaubend, können wir lassen zeigen die Dichte des Graphen an. Dann, oder besetzt die Angrenzen-Listendarstellung mehr Raum genau wenn. So muss ein Graph tatsächlich spärlich sein, um eine Angrenzen-Listendarstellung zu rechtfertigen.

Außer dem Raumumtausch erleichtern die verschiedenen Datenstrukturen auch verschiedene Operationen. Entdeckung aller Scheitelpunkte neben einem gegebenen Scheitelpunkt in einer Angrenzen-Liste ist so einfach wie das Lesen der Liste. Mit einer Angrenzen-Matrix muss eine komplette Reihe stattdessen gescannt werden, der O (n) Zeit nimmt. Ob es einen Rand zwischen zwei gegebenen Scheitelpunkten gibt, kann sofort mit einer Angrenzen-Matrix bestimmt werden, während man Zeit verlangt, die zum minimalen Grad der zwei Scheitelpunkte mit der Angrenzen-Liste proportional ist.

Weiterführende Literatur

Links

• Fluffschack - ein javanisches Bildungswebanfang-Spiel, das die Beziehung zwischen Angrenzen matrices und Graphen demonstriert.
• Offene Datenstrukturen - Abschnitt 12.1 - AdjacencyMatrix: Das Darstellen eines Graphen durch eine Matrix
• Café-Mathematik: Angrenzen Matrices von Graphen: Anwendung des Angrenzens matrices zur Berechnungserzeugen-Reihe von Spaziergängen.