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 Bearbeiten
Sei eine Matrix mit reellen Einträgen. Dann ist der Adjazenzgraph ohne Kantengewichte von definiert als
- Die Knotenmenge
- Die Kantenmenge . Dabei ist genau dann wenn von 0 verschieden ist
Will man einen gewichteten Adjazenzgraph erstellen, so erhält die Kante das Gewicht , falls dieses von 0 verschieden ist.
Diese Definition entspricht der Interpretation der Matrix als eine Adjazenzmatrix und der Rekonstruktion des Graphen aus dieser.
Eigenschaften Bearbeiten
Wie auch bei der Adjazenzmatrix schlagen sich einige Eigenschaften der Matrix im Adjazenzgraph wieder:
- Der Adjazenzgraph ist ungerichtet genau dann wenn die Matrix symmetrisch ist.
- Der Adjazenzgraph ist schleifenfrei genau dann wenn alle Diagonaleinträge von gleich 0 sind.
- Der Adjazenzgraph ist genau dann stark zusammenhängend, wenn die Matrix irreduzibel ist.
Verwendung Bearbeiten
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 Bearbeiten
- Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer, Berlin 2012, ISBN 978-3-642-32185-6.