imported>Crazy1880: tk k

2021-07-13T12:42:47Z

tk k

Neue Seite

Ein '''Adjazenzgraph''' ist ein Konzept der [[Graphentheorie]], das jeder [[Matrix (Mathematik)|Matrix]] einen [[Graph (Graphentheorie)|Graph]] zuordnet. Damit wird eine Verbindung von [[Lineare Algebra|Linearer Algebra]] und Graphentheorie hergestellt, die es erlaubt, Begriffe und Lösungskonzepte zu übertragen.

== Definition ==

[[Datei:Adjazenzgraph.svg|mini|Der kantengewichtete Adjazenzgraph der Matrix <math>A=
\begin{bmatrix}
0 & 3 & 0 & 0 \\
2 & 0 & 4 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 2 & 0
\end{bmatrix}
</math>. Es existiert kein Pfad von Knoten 3 zu Knoten 2, die Matrix ist also [[Irreduzible Matrix|reduzibel]]. Da alle Diagonaleinträge von <math>A</math> gleich 0 sind, ist der Graph schleifenfrei.]]

Sei <math>A \in \mathbb{R}^{n \times n}</math> eine Matrix mit reellen Einträgen. Dann ist der Adjazenzgraph ohne Kantengewichte <math>G_A=(V,E)</math> von <math>A</math> definiert als
* Die Knotenmenge <math>V=\{1, \ldots, n\}</math>
* Die Kantenmenge <math>E</math>. Dabei ist <math>(i,j) \in E</math> genau dann wenn <math>a_{i,j}</math> von 0 verschieden ist

Will man einen gewichteten Adjazenzgraph erstellen, so erhält die Kante <math>(i,j)</math> das Gewicht <math>a_{i,j}</math>, falls dieses von 0 verschieden ist.

Diese Definition entspricht der Interpretation der Matrix <math>A</math> als eine [[Adjazenzmatrix]] und der Rekonstruktion des Graphen aus dieser.

== Eigenschaften ==

Wie auch bei der Adjazenzmatrix schlagen sich einige Eigenschaften der Matrix im Adjazenzgraph wieder:
* Der Adjazenzgraph ist ungerichtet genau dann wenn die Matrix <math>A</math> [[Symmetrische Matrix|symmetrisch]] ist.
* Der Adjazenzgraph ist schleifenfrei genau dann wenn alle Diagonaleinträge von <math>A</math> gleich 0 sind.
* Der Adjazenzgraph ist genau dann [[Zusammenhang (Graphentheorie)|stark zusammenhängend]], wenn die Matrix <math>A</math> irreduzibel ist.

== Verwendung ==

Wie auch die Adjazenzmatrix schlägt der Adjazenzgraph eine Verbindung zwischen Linearer Algebra und Graphentheorie und erlaubt somit, Lösungskonzepte beider Themen zu verbinden. Beispiel hierfür ist die Irreduzibilität von Matrizen. Diese lässt sich mit Mitteln der Linearen Algebra nur schwer überprüfen. Erstellt man den Adjazenzgraphen und überprüft diesen auf starken Zusammenhang, so ist dies äquivalent zur Überprüfung der Irreduzibilität der Matrix.
Außerdem bieten sich Adjazenzgraphen zur Veranschaulichung von [[Markow-Kette]]n an, da jeder [[Übergangsgraph]] Adjazenzgraph einer [[Übergangsmatrix|zeilenstochastischen Matrix]] ist.

== Literatur ==
* {{Literatur |Autor=[[Peter Knabner]], [[Wolf Barth (Mathematiker)|Wolf Barth]] |Titel=Lineare Algebra |TitelErg=Grundlagen und Anwendungen |Reihe=Springer-Lehrbuch |Verlag=Springer |Ort=Berlin |Datum=2012 |ISBN=978-3-642-32185-6}}

[[Kategorie:Graph]]
[[Kategorie:Graphentheorie]]

Adjazenzgraph - Versionsgeschichte

imported>Crazy1880: tk k