Zurückblättern Weiterblättern Übergeordnetes Thema Sachgebiet Hauptinhaltsverzeichnis Stichwortverzeichnis Hilfeseiten        


Adjazenzmatrix

Endliche Graphen kann man wie folgt durch eine Matrix beschreiben: Es sei ein Graph mit und Dabei bezeichne die Anzahl der Kanten von nach Bei ungerichteten Graphen werden Schlingen doppelt gezählt; bei gerichteten Graphen zählt man Schlingen einfach. Die Matrix vom Typ mit wird Adjazenzmatrix genannt. Ist der Graph zusätzlich schlicht, dann hat die Adjazenzmatrix die folgende Gestalt:
(5.332)

D.h. in der Matrix steht in der -ten Zeile und -ten Spalte genau dann eine 1, wenn eine Kante von nach verläuft.
Für ungerichtete Graphen ist die Adjazenzmatrix symmetrisch.

Beispiel A

Neben der Abbildung ist die Adjazenzmatrix des gerichteten Graphen gezeigt.



Beispiel B

Neben der Abbildung ist die Adjazenzmatrix des ungerichteten schlichten Graphen gezeigt.