Darstellungen für Graphen

Es gibt verschiedene Möglichkeiten, einen Graphen G = (E, K) mit

E	= { e₁, …, e_n },	e_i ≠ e_j	für alle i ≠ j,
K	= { k₁, …, k_m },	k_i ≠ k_j	für alle i ≠ j,

darzustellen. Die erste haben wir in obigen Diagrammen bereits verwendet:

1. Erstellung eines Ecken-Kanten-Diagramms

Ein (mathematischer) Graph lässt sich als (gezeichneter) Graph darstellen. Wir zeichnen hierzu benannte Ecken und verbinden je zwei Ecken, die durch eine Kante verbunden sind, durch eine Linie. Diese Linie muss kein Geradenstück sein und sie kann andere Linien schneiden, darf aber nicht durch weitere Ecken laufen. Die Ecken selbst können wir in verschiedenen Weisen darstellen, als Punkte mit Namen, lediglich als Namen oder wie bisher als Kreise, die die Namen der Ecken enthalten.

Die graphische Darstellung ist keineswegs eindeutig. Wie ein Graph im Hinblick auf bestimmte Ziele am besten zu zeichnen ist, ist eine Kunst für sich!

2. Bildung der Adjazenz-Matrix

Die Adjazenz-Matrix oder Nachbarschafts-Matrix des Graphen G ist die n × n-Matrix A = (a_ij)_{1 ≤ i, j ≤ n} mit den Einträgen

$a_{ij} = { \begin{matrix} 1 & falls {e_{i}, e_{j}} \in K, \\ 0 & sonst. \end{matrix}$

Die Adjazenz-Matrix erlaubt eine rechnerische Kodierung eines Graphen und den Einsatz von Methoden der linearen Algebra. Das Gleiche gilt für:

3. Bildung der Inzidenz-Matrix

Die Inzidenz-Matrix oder Ecken-Kanten-Matrix des Graphen G ist die n × m-Matrix B = (b_ij)_{1 ≤ i ≤ n, 1 ≤ j ≤ m} mit den Einträgen

$b_{ij} = { \begin{matrix} 1 & falls e_{i} \in k_{j}, \\ 0 & sonst. \end{matrix}$

In jeder Spalte von B stehen genau zwei Einsen. Die Zeilenindizes der beiden Einsen entsprechen einer Kante. Da wir auch eine leere Kantenmenge zulassen, ist die Inzidenz-Matrix möglicherweise nullspaltig.

4. Bildung der Adjazenz-Liste

Schließlich können wir auch eine Tabelle angeben, die für jede Ecke a alle Nachbarecken auflistet, d. h. alle Ecken b mit { a, b }  ∈  K.

Umgekehrt können diese Darstellungen auch zur Definition eines Graphen verwendet werden, etwa:

„Sei G = (E, K) der durch das folgende Diagramm definierte Graph.“

„Sei G = (E, K) der durch folgende Adjazenz-Matrix definierte Graph.“

Für die Matrizen-Darstellungen gilt: Ist die Eckenmenge E von der kanonischen Form E = { 1, …, n }, so ist der Graph G = (E, K) durch seine Adjazenz- oder Inzidenz-Matrix bestimmt. Andernfalls müssen neben der Matrix noch die Namen e₁, …, e_n der Ecken angegeben werden. Wird ein Graph durch eine Matrix ohne explizite Angaben einer Eckenmenge definiert, so nehmen wir stillschweigend E = { 1, …, n } an. Die Ecken entsprechen dann den Zeilenindizes der Matrix.

Beispiel

Sei G = (E, K) mit

E = { 1, 2, 3, 4 }, K = { { 1, 2 }, { 1, 3 }, { 1, 4, }, { 2, 3 }, { 3, 4 } }.

Dann hat G die folgenden Darstellungen:

(1)	Ecken-Kanten-Diagramm

(2)	Adjazenz-Matrix A = $( \begin{matrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{matrix} )$

(3)	Inzidenz-Matrix B = $( \begin{matrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \end{matrix} )$

(4)

Adjazenz-Liste

Ecke	Liste der Nachbarecken
1	2, 3, 4
2	1, 3
3	1, 2, 4
4	1, 3

Eine Adjazenz-Matrix A hat die Hauptdiagonale 0 = (0, …, 0), da unsere Graphen schlingenfrei sind. Weiter ist A symmetrisch, da { e_i, e_j } = { e_j, e_i } für alle i, j.

Es ist instruktiv zu beobachten, wie sich Symmetrie-Eigenschaften von Adjazenz-Matrizen auf graphische Darstellungen auswirken:

Beispiel

Sei G = (E, K) der Graph mit der Adjazenz-Matrix

A = $( \begin{matrix} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \end{matrix} )$ .

Dann hat G die folgende graphische Darstellung: