\( \newcommand{\lower}{\textnormal{lower}} \newcommand{\upper}{\textnormal{upper}} \newcommand{\array}{\textnormal{array}} \newcommand{\depth}{\textnormal{depth}} \newcommand{\height}{\textnormal{height}} \newcommand{\BST}{\textnormal{BST}} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\lognpone}{\ceil{\log_2(n+1)}} \newcommand{\bitsize}{\textnormal{bitSize}} \newcommand{\mult}{\textnormal{mult}} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\pfrac}[2]{\left(\frac{#1}{#2}\right)} \)

6. Graphen

6.1 Beispiele, Definition, Repräsentierung

Hier ist ein Graph.
Er besteht aus den fünf Knoten \(a,b,c,d,e\) und hat sechs Kanten. Hier ist die formale Definition:
Definition Ein Graph ist ein Paar \((V, E)\) mit \(E \subseteq {V \choose 2}\). \(V\) ist die Knotenmenge und \(E\) ist die Kantenmenge.

Wir schreiben \(V\), weil Knoten auf Englisch vertex heißt (Plural: vertices) und \(E\), weil Kante auf Englisch edge heißt. Die Notation \({V \choose 2}\) bezeichnet die Menge aller Teilmengen der Größe 2 von \(V\). Der Graph im obigen Beispiel wäre also \(G = (V, E)\) mit \(V = \{a,b,c,d,e\}\) und \(E = \{\{a,b\}, \{b,c\}, \{a,c\}, \{b,d\}, \{c,d\}, \{a,e\}\}\). Beachten Sie, dass der mathematische Begriff Menge nur "enthalten" und "nicht enthalten" kennt, nicht "erstes Element"; so sind \(\{a,b\}\) und \(\{b,a\}\) die gleiche Menge. Für den Graphen \(G\) heißt das, das die Kanten ungerichtet sind.

Traditionall bezeichnet \(n := |V|\) und \(m := |E|\).

Pfade, Kreise, Kantenzüge, geschlossene Kantenzüge

Ein Graph \(G\)
Ein Pfad (path) in \(G\)
Ein Kreis (cycle) in \(G\)

Für den Moment verzichte ich auf eine formale Definition. Es sei aber noch hinzugefügt, dass Pfade und Kreise sich nicht selbst schneiden dürfen:

Dies ist kein Pfad (aber ein Kantenzug / walk)
Dies ist kein Kreis (aber ein geschlossener Kantenzug / closed walk)

Graphen repräsentieren

Wie können wir einen Graphen im Rechner darstellen? Grundsätzlich gibt es zwei Methoden: als Adjazenzmatrix oder mit Adjazenzlisten. An einem Beispiel:
Ein Graph \(G\)
Als Adjazenzmatrix
Als Liste von Adjazenzlisten

Formal definieren wir die Adjazenzmatrix \(A\) von \(G = (V,E)\) als eine \(n \times n\)-Matrix, wobei der Eintrag \(A_{u,v}\) gleich 1 ist, wenn \( \{u,v\} \in E\) und 0 sonst (wir haben oben die 0-Einträge der Übersichtlichkeit halber weggelassen). Diese Darstellung benötigt \(\Theta(n^2)\) Speicherplatz, was in den meisten Fällen zu viel ist. Zwei Vorteile dieser Darstellung: (1) Sie können in \(O(1)\) testen, ob eine Kante \(\{u,v\}\) existiert; (2) die ganze Maschinerie der linearen Algebra steht Ihnen zu Diensten.

In 90% der Fälle (Schätzung aus dem Bauch heraus) verwenden wir für Algorithmen die Darstellung mit Adjazenzlisten. Sie benötigt \(\Theta(m \log n)\) Platz.

Übungsaufgabe Eklären Sie, warum die Darstellung mit Adjazenzlisten \(\Theta(m \log n)\) braucht, wo es doch eher nach \(\Theta(m)\) aussieht.

Graphen kodieren

Fürs erste wählen wir eine einfache und etwas primitive Art der Codierung für Graphen. Die Knotenmenge ist immer \(V = \{0,1,\dots,n-1\}\). Sei \(E = \{\{u_1, v_1\}, \dots, \{u_m, v_m\}\}\). Dann codieren wir \(G = (V,E)\) als Textdatei im Format

n m 
u_1 v_1 
u_2 v_2 
... 
u_m v_m

Dies ist sicherlich nicht sehr human readable und nicht sehr flexibel. Es wird uns aber erlauben, mit unserem Programmen Graphen einzulesen, ohne erst ausgefeilte Parser schreiben zu müssen. Außerdem ist es das übliche Format für graphentheoretische Aufgaben beim International Collegiate Programming Content (Wollen Sie daran teilnehmen? Vielleicht können wir ein HSZG-Team auf die Beine stellen).

Übungsaufgabe Codieren Sie in diesem Format.