Was ist ein Graph?

Ein Graph $G$ ist ein Paar $(V,E)$ (Keine Sorge … im Applet unten werden die nachfolgenden Formalia konkretisiert!). Das Paar $G = (V,E)$ besteht dabei aus einer Menge von Knoten (engl. verticies) $V$ und einer Menge von Kanten (engl. edges) $E$. Graphen können bzgl. der Wahl ihrer Kantenmenge $E$ grob klassifiziert werden. Zwei wichtige Klassen von Graphen sind

• ungerichtete Graphen (ohne Mehrfachkanten): $E$ ist eine Teilmenge der Menge aller zweielementigen Mengen von $V$.
• gerichtete Graphen (ohne Mehrfachkanten): $E$ ist eine Teilmenge des kartesischen Produkts $V \times V$. Man kann jeden ungerichtete Graphen $G = (V,E)$ als Spezialfall eines gerichteten Graphen $\tilde{G} = (\tilde{V},\tilde{E})$ interpretieren. Zu diesem Zweck wählt man $\tilde{V} := V$ und jede ungerichtete Kante wird mittels

\[ (v,w) \in \tilde{E} ~ :\Leftrightarrow ~ {v,w} \in E, \]

über das jeweilige Paar der gerichteten Hin- und Rückkante repräsentiert. Einheitlich werden wir die Existenz von Kanten in ungerichteten wie gerichteten Graphen wie folgt notieren:

\[ v E w :\Leftrightarrow \left\{ \begin{array}{ll} {v, w} \in E, & \text{falls} ~ G ~ \text{ungerichteter Graph} \\ (v,w) \in E, & \text{falls} ~ G ~ \text{gerichteter Graph} \end{array} \right. \]

Im Kontext der Diskreten Mathematik seien die Mengen $V$ und $E$ jeweils endliche Mengen. In diesem Fall bieten sich neben der mengentheoretischen Repräsentation über das Paar $G = (V,E)$ eines gerichteten bzw. ungerichteten Graphen, noch folgende weitere Darstellungsformen an:

• Knotenmenge $V$ + Adjazenzmatrix
• Knotenmenge $V$ + Adjazenzliste

Adjazenzmatrix

Einem gerichteten bzw. ungerichteten Graphen $G = (V,E)$ lässt sich auf natürliche Weise eine $(0,1)$-Matrix $A_G$ zuordnen, welche man auch als die Adjazenzmatrix von $G$ bezeichnet. Falls $n := |V|$ die Anzahl der Knoten von $G$ ist, können wir letztere durch Wahl einer beliebigen aber gleichbleibenden Nummerierung mit den Zahlen von $1$ bis $n$ identifizieren, sprich $V \cong {1, \ldots, n}$. Die Adjazenzmatrix $A_G = (a_{i,j})_{i,j \in \{1, \ldots, n\}}$ sei nun eine Matrix mit $n$ Spalten und $n$ Zeilen, wobei die Einträge $a_{i,j}$ wie folgt definiert sind:

\[ a_{i,j} := \left\{ \begin{array}{ll} 1, & i E j \\ 0, & \text{sonst.} \end{array} \right. \]

Die Einträge der Adjazenzmatrix $A_G$ spiegeln die Tatsache wieder, ob es in $G$ eine Kante von Knoten $i$ nach Knoten $j$ gibt. Aufgrund der Symmetrie ${i,j} = {j,i}$, ist die Adjazenzmatrix eines ungerichteten Graphen symmetrisch, d.h. es gilt $a_{i,j} = a_{j,i}, ~ \forall i,j \in {1, \ldots, n}$.

Der Speicherbedarf dieser Repräsentationsform liegt offenbar bei $\mathcal{O}(|V|^2)$, d.h. er ist proportional zum Quadrat der Anzahl von Knoten in $G$, und ist unabhängig von der Kantenanzahl $|E|$.

Adjazenzliste

Bei der Repräsentation eines Graphen $G = (V,E)$ durch seine Adjazenzliste speichert man für jeden Knoten die Liste seiner Nachbarn (Ein Knoten $v \in V$ ist ein Nachbar von $w \in V$, falls $v E w$ gilt. Bei ungerichteten Graphen werden somit bei einer Nachbarschaft von $v$ und $w$ immer zwei Listeneinträge benötigt.).

Der Speicherbedarf dieser Repräsentationsform liegt bei $\mathcal{O}(|V| + |E|)$, d.h. er ist proportional zur Summe der Anzahl von Knoten und Kanten in $G$. Aus diesem Grund ist die Repräsentation eines Graphen $G$ über seine Adjazenzliste - trotz des Verwaltungsmehraufwandes - oftmals effizienter bei der Lösung von graphentheoretischen Problemen im Vergleich zur Repräsentation von $G$ über die Adjazenzmatrix $A_G$.

Graphisch & Applet

Im nachfolgenden Applet kann man sich mit den verschiedenen Repräsentationsformen eines Graphen $G = (V,E)$ vertraut machen. Neben der mengentheoretischen Repräsentation von $G$ über das Paar $(V,E)$ werden zeitgleich die Adjazenzmatrix $A_G$ und die Adjazenzliste von $G$ dargestellt. Die Eingabe und Manipulation eines beliebigen $G$ erfolgt dabei wohl über die natürlichste Art der Graphenrepräsentation. Die Knoten von $G$ sind hierbei Punkte in der Zeichenebene und die Kanten von $G$ ungerichtete bzw. gerichtete Verbindungssegmente zwischen benachbarten Knoten.

Zur Bedienung des Applets:

• Modus Knoten oder Kante anwählen und dann per Click/Drag beliebigen Graphen zeichnen.
• Der Taster gerichtete/ungerichtete Graphen löscht den aktuellen Graphen und wechselt den Modus gerichtete Graphen/ungerichtete Graphen.

GraphIntro.cdy (Dieses Applet kann in Cinderella ausgeführt werden.)