Adjazenzgraph

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

Definition

Der kantengewichtete Adjazenzgraph der Matrix $A={\begin{bmatrix}0&3&0&0\\2&0&4&0\\0&0&0&1\\0&0&2&0\end{bmatrix}}$. Es existiert kein Pfad von Knoten 3 zu Knoten 2, die Matrix ist also reduzibel. Da alle Diagonaleinträge von $A$ gleich 0 sind, ist der Graph schleifenfrei.

Sei $A\in \mathbb {R} ^{n\times n}$ eine Matrix mit reellen Einträgen. Dann ist der Adjazenzgraph ohne Kantengewichte $G_{A}=(V,E)$ von $A$ definiert als

• Die Knotenmenge $V=\{1,\ldots ,n\}$
• Die Kantenmenge $E$. Dabei ist $(i,j)\in E$ genau dann wenn $a_{i,j}$ von 0 verschieden ist

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

Diese Definition entspricht der Interpretation der Matrix $A$ 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 $A$ symmetrisch ist.
• Der Adjazenzgraph ist schleifenfrei genau dann wenn alle Diagonaleinträge von $A$ gleich 0 sind.
• Der Adjazenzgraph ist genau dann stark zusammenhängend, wenn die Matrix $A$ 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-Ketten an, da jeder Übergangsgraph Adjazenzgraph einer zeilenstochastischen Matrix ist.

Literatur

• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer, Berlin 2012, ISBN 978-3-642-32185-6.