Repräsentation von Graphen im Computer

Für die Repräsentation von Graphen im Computer gibt es im Wesentlichen zwei gebräuchliche Formen, die Adjazenzmatrix und die Adjazenzliste. Alternative Bezeichnungen sind Nachbarschaftsmatrix und Nachbarschaftsliste. Die Bedeutung der beiden Begriffe liegt darin, dass praktisch jede algorithmische Lösung graphentheoretischer Probleme auf wenigstens eine der beiden Repräsentationen zurückgreift. Eine weitere, aber seltener genutzte Möglichkeit zur Darstellung von Graphen im Computer ist die Inzidenzmatrix, die man auch als Knoten-Kanten-Matrix bezeichnet.

Adjazenzmatrix (Nachbarschaftsmatrix)

Ein Graph mit n Knoten kann durch eine $n \times n$-Matrix repräsentiert werden. Dazu nummeriert man die Knoten von 1 bis n durch und trägt in die Matrix die Beziehungen der Knoten zueinander ein.

Ungerichteter Graph	Adjazenzmatrix
	$\begin{pmatrix} 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 1 & 1\\ 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0\\ \end{pmatrix}$

In ungerichteten Graphen ohne Mehrfachkanten wird in die i-te Zeile und j-te Spalte eine 1 eingetragen, wenn der i-te und j-te Knoten benachbart, d.h. durch eine Kante verbunden sind. Andernfalls wird eine 0 eingetragen. Da die Relation „benachbart“ symmetrisch ist (wenn Knoten i mit Knoten j benachbart ist, dann ist auch Knoten j mit Knoten i benachbart), ist auch die Adjazenzmatrix symmetrisch.

In gerichteten Graphen ohne Mehrfachkanten wird in die i-te Zeile und j-te Spalte eine 1 eingetragen, wenn der i-te Knoten Vorgänger des j-ten Knoten ist. Andernfalls wird eine 0 eingetragen. Damit ergibt sich sowohl für ungerichtete wie auch für gerichtete Graphen $G=(V,E)$ mit Knotenmenge V und Kantenmenge E folgende komponentenweise Definition für die Adjazenzmatrix $A$:

$a_{i,j}= \begin{cases} 1 \; \text{falls} \; (i,j) \in E \\ 0 \; \text{sonst} \end{cases}$

Die Matrix $A$ ist genau dann symmetrisch, wenn der Graph es ist. Ihre Hauptdiagonale enthält nur Nullen, wenn der Graph schleifenfrei ist. Dies ist genau der Grund, warum man gerichtete Graphen, die symmetrisch sind, auch ungerichtet nennt. Sind sie zudem schleifenfrei, sind es einfache bzw. schlichte Graphen. Ihre Adjazenzmatrix ist dann nämlich äquivalent zu der eines ungerichteten Graphen, und diese sind ein Spezialfall der gerichteten Graphen.

In Graphen mit Mehrfachkanten trägt man in die i-te Zeile und j-te Spalte die Vielfachheit von {i,j} in ungerichteten Graphen bzw. (i,j) in gerichteten Graphen ein. Auch an dieser Stelle sieht man leicht, warum Graphen ohne Mehrfachkanten als Spezialfälle von Graphen mit Mehrfachkanten betrachtet werden können.

In kantengewichteten Graphen trägt man häufig auch das Kantengewicht der jeweiligen Kante ein, wobei in Abhängigkeit vom betrachteten Problem Knoten, die nicht durch eine Kante verbunden sind, mit 0 oder ∞ markiert werden. (Siehe auch: Entfernungstabelle). Damit ergibt sich für einen kantengewichteten Graph $G=(V,E,c)$ die komponentenweise Definition der Adjazenzmatrix $A$ durch

$a_{i,j}= \begin{cases} c_{ij} \; \text{falls} \; (i,j) \in E \\ 0 \; \text{sonst} \end{cases}$

Insbesondere stellt die Adjazenzmatrix eine Verbindung zwischen der linearen Algebra und der Graphentheorie her, da sich einige Eigenschaften von Graphen in der Adjazenzmatrix wiederfinden. Ist die Adjazenzmatrix z.B. irreduzibel, so ist der Graph stark zusammenhängend. Als Adjazenzraum eines Graphen bezeichnet man den Vektorraum, der von den Spalten der Adjazenzmatrix aufgespannt wird. Durch Summierung der ersten $n$ Potenzen einer Adjazenzmatrix inklusive der Einheitsmatrix als nullter Potenz und Setzen aller Elemente ungleich $0$ auf $1$ erhält man eine Matrix, die für jeden Knoten angibt, welche Knoten von ihm aus in höchstens $n$ Schritten erreichbar sind. Ändert sich diese Matrix vom $n$-ten auf den $(n+1)$-ten Schritt nicht, hat man so die Erreichbarkeitsmatrix des Graphen ermittelt.

Hypergraphen lassen sich nicht durch eine Adjazenzmatrix darstellen.

Adjazenzliste (Nachbarschaftsliste)

Die Adjazenzliste wird in ihrer einfachsten Form durch eine einfach verkettete Liste aller Knoten des Graphen dargestellt, wobei jeder Knoten eine Liste aller seiner Nachbarn (in ungerichteten Graphen) bzw. Nachfolger (in gerichteten Graphen) besitzt. Vielfachheiten der Kanten, Knotengewichte, und Kantengewichte werden meist in Attributen der einzelnen Elemente gespeichert. Je nach Problemstellung kann es notwendig sein, statt einer einfach verketteten Liste eine doppelt verkettete Liste zu verwenden und in gerichteten Graphen zusätzlich zur Liste der Nachfolger eine Liste der Vorgänger zu verwalten.

Definition

Mit $V$ als Menge der Knoten und $E$ als Menge der Kanten sei ein Graph $G =\left(V, E \right)$ (ohne Mehrfachkanten) gegeben. Das heißt es ist $E\subset V\times V$ und es ist $(x,y)\in E$ genau dann, wenn der Graph eine Kante von $x$ nach $y$ enthält. Zu jedem Knoten $x\in V$ ist die Adjazenzliste definiert als

$A(x)=\left\{ y \in V: (x, y) \in E \right\}$,

das heißt $A(x)$ ist für jeden Knoten $x$ die Liste aller Nachbarn (bzw. Nachfolger) $y$.

Inzidenzmatrix

→ Der hier beschriebene Begriff einer Inzidenzmatrix kann bei ungerichteten Graphen als Spezialfall der in Inzidenzstruktur#Inzidenzmatrix zur Beschreibung einer endlichen Inzidenzstruktur erläuterten Matrix angesehen werden.

Ein Graph mit $n$ Knoten und $m$ Kanten kann auch durch eine $n \times m$-Matrix repräsentiert werden. Dazu nummeriert man die Knoten von $1$ bis $n$ und die Kanten von $1$ bis $m$ durch und trägt in die Matrix die Beziehungen der Knoten zu den Kanten ein.

Jede Spalte der Inzidenzmatrix enthält genau zwei von Null verschiedene Einträge. In ungerichteten Graphen zweimal die $1$ und in schleifenfreien gerichteten Graphen einmal die $1$ (Startknoten) und einmal die $-1$ (Endknoten).

Für einen ungerichteten Graphen $G = (V, E)$ mit $V = \lbrace v_1, ..., v_n \rbrace$ und $E = \lbrace e_1, ..., e_m \rbrace$ ist die Inzidenzmatrix $B = (b_{i, j})$ formal also definiert durch:

$b_{ij} := \begin{cases} 1, & \text{ falls } v_i \in e_j \\ 0, & \text{ sonst} \end{cases}$

Für einen schleifenfreien, gerichteten Graphen $G = (V, E)$ mit $V = \lbrace v_1, ..., v_n \rbrace$ und $E = \lbrace e_1, ..., e_m \rbrace$ ist die Inzidenzmatrix $B = (b_{i, j})$ definiert durch:

$b_{ij} := \begin{cases} 1, & \text{ falls } e_j=(v_i,x) \\ 0, & \text{ falls } v_i \notin e_j \\ -1, & \text{ falls } e_j=(x,v_i) \end{cases}$

wobei $x$ hier einen beliebigen Knoten darstellt.

Einen Anwendungsfall stellt die Inzidenzmatrix eines Petri-Netzes dar.

Beispiel

Der im Bild dargestellte Graph hat beispielsweise die folgende Inzidenzmatrix. Die Zahlen an den Kanten sind dabei nicht mit Gewichtungen der Kanten zu verwechseln. Sie beschreiben die Namen der Kanten $(e_1,e_2,\ldots,e_6)$, die in der Matrix als Spalten wiederzufinden sind.

$\Leftrightarrow\begin{pmatrix} e_1 & e_2 & e_3 & e_4 & e_5 & e_6\\ 1&0&0&0&1&0& v_1\\ 1&1&0&0&0&1& v_2\\ 0&1&1&0&0&0& v_3\\ 0&0&1&1&0&0& v_4\\ 0&0&0&1&1&1& v_5\\ \end{pmatrix}$

Vergleichende Betrachtungen zwischen Adjazenzmatrix und Inzidenzmatrix

Inzidenzmatrizen sind zwar aufwändiger zu implementieren und zu verwalten, bieten aber eine Reihe von Vorteilen gegenüber Adjazenzmatrizen. Zum einen verbrauchen sie bei fester Anzahl von Kanten stets nur linear viel Speicherplatz bezüglich der Anzahl der Knoten, was insbesondere bei dünnen Graphen (also Graphen mit wenig Kanten) von Vorteil ist, während die Adjazenzmatrix quadratischen Platzbedarf bezüglich der Anzahl Knoten besitzt (dafür aber kompakter bei dichten Graphen, also Graphen mit vielen Kanten ist). Zum anderen lassen sich viele graphentheoretische Probleme nur mit Adjazenzlisten in linearer Zeit lösen. In der Praxis verwendet man daher meist diese Form der Repräsentation.

Quellen

•  Gunter Saake, Kai-Uwe Sattler: Algorithmen & Datenstrukturen: Eine Einführung mit Java. 2. überarbeitete und erweiterte Auflage Auflage. dpunkt.verlag, Heidelberg 2004, ISBN 3-89864-255-0.
•  Thomas H. Cormen, Charles Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – Eine Einführung. 2. Auflage. Oldenbourg Wissenschaftsverlag, München 2007, ISBN 978-3-486-58262-8, S. 531-533.
•  Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). 1. Auflage. Springer, Berlin 2012, ISBN 978-3-642-32185-6 (996 Seiten).