Definition Was ist eine Adjazenzmatrix?

Eine Adjazenzmatrix bildet einen Graph mit seinen Knoten und Kanten in einer Matrix ab. Die Adjazenzmatrix kann für unterschiedliche Graphenarten wie gerichtete, ungerichtete oder gewichtete Graphen verwendet werden und ermöglicht den Einsatz der Methoden linearer Algebra.

Anbieter zum Thema

Fujitsu Technology Solutions GmbH

Confluent Germany GmbH

Xpand Solutions GmbH

Der Begriff „Adjazenz“ stammt aus dem Lateinischen und bedeutet „Nachbarschaft“. Mithilfe einer Adjazenzmatrix lassen sich Graphen mit ihren Knoten und Kanten in einer Matrix abbilden. Die Matrix speichert die Beziehungen der Knoten untereinander. Jeder Knoten repräsentiert in der Matrix ein Zeile und ein Spalte. Die Matrix ist bei einer Anzahl von N Knoten N x N groß. Die Einträge in den Spalten und Zeilen zeigen, ob Knoten miteinander verbunden sind.

Die Zahl „0“ steht für keine Verbindung (keine Kante), die Zahl „1“ für eine existierende Verbindung. Adjazenzmatrizen lassen sich für verschiedene Arten von Graphen wie gerichtete Graphen, ungerichtete Graphen oder gewichtete Graphen verwenden. Bei gewichteten Graphen stehen nicht die Werte „0“ oder „1“, sondern Zahlen als Gewichtungen in der Matrix. Die Adjazenzmatrix verbindet die Graphentheorie mit der linearen Algebra.

Durch die Abbildung eines Graphen in einer Matrix lassen sich die Methoden der linearen Algebra auf Graphen anwenden und Graphenoperationen werden zu Matrixoperationen. Es können beispielsweise Analysen durchgeführt werden, die die günstigsten Verbindung zwischen zwei Knoten errechnen. Weitere Anwendungsmöglichkeiten sind:

• das Ermitteln der erreichbaren Knoten

• das Errechnen von Pfadlängen

• die Analyse auf Schleifenfreihei

Ein Vorteil der Adjazenzmatrix ist, dass die Anzahl der Kanten keine Rolle für die Größe der Matrix spielt, da sie lediglich von der Anzahl der Knoten abhängig ist. Die Matrix eignet sich deshalb sehr gut für die rechnerische Verarbeitung von Graphen mit vielen Verbindungen (Kanten). Für nur schwach verbundene Graphen mit vielen Knoten ist die Adjazenzmatrix weniger gut geeignet, da vielen Nullen in der Matrix vorhanden sind, die Speicherplatz belegen. In diesen Fällen sind Adjazenzlisten sinnvoller.

Die verschiedenen Adjazenzmatrizen für unterschiedliche Graphen

Mit Adjazenzmatrizen lassen sich unterschiedliche Graphen abbilden. Je nach Graphenart besitzen die Matrizen spezifische Eigenschaften. Im Folgenden ein kurzer Überblick der Adjazenzmatrizen für ungerichtete, gerichtete und gewichtete Graphen:

Die Adjazenzmatrix eines ungerichteten Graphen

Eine Verbindung (Kante) zwischen zwei Knoten in einem ungerichteten Graphen ist in beide Richtungen gültig. Überträgt man die Verbindungen in die Matrix, erhält man eine symmetrische, an der Diagonalen gespiegelte Adjazenzmatrix. Der gespiegelte Teil enthält redundante Informationen und kann weggelassen werden. Oft hat die Darstellung der Matrix daher eine Dreiecksform.

Die Adjazenzmatrix eines gerichteten Graphen

Beim gerichteten Graphen sind die Verbindungen zwischen den Knoten jeweils nur in einer Richtung gültig. Im Graphen erfolgt die Darstellung der Richtung mit einem Pfeil. Für die Adjazenzmatrix haben die gerichteten Kanten zur Folge, dass keine Symmetrie mehr besteht.

Die Adjazenzmatrix für Graphen mit Kantengewichten

In gewichteten Graphen haben die Kanten sogenannte Kosten oder Gewichte. In einer Matrix für gewichtete Graphen werden keine Nullen und Einsen, sondern die Werte für das jeweilige Gewicht der Kante zwischen den Knoten eingetragen. Diese Adjazenzmatrizen werden beispielsweise für Algorithmen zur Ermittlung günstigster Wege verwendet.

Zusammenhang zwischen der Adjazenzmatrix, Inzidenzmatrix und der Adjazenzliste

Oft fallen im Zusammenhang mit der Adjazenzmatrix die Begriffe der Adjazenzliste oder der Inzidenzmatrix. Eine Adjazenzliste zeigt ausgehend von einem Knoten seine jeweiligen Kante in Listenform. Diese Art der Darstellung eignet sich im Gegensatz zur Adjazenzmatrix für schwach verbundene Graphen. Das Speichern von viele Nullen, wie es die Adjazenzmatrix in diesem Fall erfordert, ist nicht notwendig, da nur die tatsächlichen Verbindungen in der Liste aufgeführt sind. Hat der Graph allerdings viele Kanten, übersteigt ab einer bestimmten Kantendichte der Speicherbedarf der Liste den Speicherbedarf einer Adjazenzmatrix.

Eine Inzidenzmatrix bildet einen Graphen ab, indem für jeden Knoten eine Zeile und für jede Kante eine Spalte verwendet wird. Der Speicherbedarf einer Inzidenzmatrix ist sowohl von der Anzahl der Kanten als auch von der Anzahl der Knoten abhängig. Bei einer großen Anzahl von Kanten benötigt eine Inzidenzmatrix mehr Speicherplatz als eine Adjazenzmatrix, bei geringer Kantenanzahl weniger.

Verwendungsmöglichkeiten der Adjazenzmatrix

Die Adjazenzmatrix wird verwendet, um Graphen in einem Computer zu speichern und Methoden der linearen Algebra auf den Graphen anzuwenden, aus denen sich Rückschlüsse auf die Eigenschaften des Graphen ziehen lassen. Realisierbar sind dadurch beispielsweise Routenplanungen, das Erstellen von Netzplänen oder weitere Analysen verschiedenster vernetzter Zusammenhänge. Beispielsweise verwendet der PageRank-Algorithmus die Adjazenzmatrix.

(ID:46021064)