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
 
Der kantengewichtete Adjazenzgraph der Matrix  . Es existiert kein Pfad von Knoten 3 zu Knoten 2, die Matrix ist also reduzibel. Da alle Diagonaleinträge von   gleich 0 sind, ist der Graph schleifenfrei.

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