Hier ist ein ungerichteter Graph.
Er hat hat sechs Knoten und acht Kanten. Eine Kante in einem gerichteten Graphen besteht aus einem Startpunkt und einem Endpunkt. Das passende mathematische Objekt ist hier das geordnete Paar. So ist beispielsweise $(2,4)$ eine Kante, $(4,2)$ jedoch nicht; $(3,3)$ ist eine, $(5,5)$ aber nicht.
Definition(Ungerichteter und gerichteter Graph). Ein ungerichteter Graph ist ein Paar \((V, E)\) mit \(E \subseteq {V \choose 2}\). \(V\) ist die Knotenmenge und \(E\) ist die Kantenmenge.
Ein gerichteter Graph ist ein Paar $(V,E)$ mit $E \subseteq V \times V$.
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 ungerichtete Graph im obigen Beispiel wäre also
\begin{align*} \left(\{a,b,c,d,e\},\{\{a,b\}, \{b,c\}, \{a,c\}, \{b,d\}, \{c,d\}, \{a,e\}\} \right) \end{align*}und der gerichtete oben wäre
\begin{align*} \left(\{1,2,3,4,5,6\},\{(1,2), (1,3),(2,4), (3,2), (3,3), (4,3), (5,3), (5,6), (6,5)\}\right) \end{align*}Traditionall bezeichnet \(n := |V|\) die Anzahl der Knoten und \(m := |E|\) die Anzahl der Kanten.
Kantenzüge, Pfade, geschlossene Kantenzüge und Kreise
Bevor ich diese Begriffe formal definiere, gebe ich ein paar Beispiele:
Und nochmal ein paar Beispiele für gerichtete Graphen:
Definition Sei $G = (V,E$ ein ungerichteter oder gerichteter Graph. Ein Kantenzug ist eine Folge $P = u_0, u_1, \dots, u_k$ mit $(u_{i-1}, u_i) \in E$ für all $1 \leq i \leq k$ (bzw. $\{u_{i-1}, u_i\} \in E$, wenn $G$ ungerichtet ist).
- Wenn alle $u_i$ verschieden sind, dann ist es ein Pfad.
- Wenn $k \geq 1$ und $u_0 = u_k$ ist, dann ist es ein geschlossener Kantenzug.
Sei $P$ ein geschlossener Kantenzug. Wenn alle Knoten bis auf $u_0, u_k$ verschieden sind (wenn also $u_1, \dots, u_k$ ein Pfad ist), dann ist $P$ ein Kreis (bei Graphen muss zusätzlich $k \geq 3$ gelten.).
Die Länge des Kantenzuges / Pfades / Kreises ist $k$, also die Anzahl der beschrittenen Kanten.
Der Fall $k = 0$ ist für Kantenzüge und Pfade ausdrücklich erlaubt. Im obigen ungerichteten Graphn ist zum Beispiel $e, a, b, c$ ein Pfad der Länge 3, und $e$ ist ein Pfad der Länge $0$. Die Bedingung $k \geq 3$ bei Kreisen in ungerichteten Graphen ist nötig, weil sonst jede Kante einen Kreis ergeben würde.
ein geschlossener Kantenzug, aber kein Kreis in $G$. Ein Kreis in einem ungerichteten Graphen enthält immer mindestens 3 Kanten.
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:
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.
Graphen kodieren
In meinen Code-Beispielen werde ich Python verwenden. Die Adjazenzliste stelle ich als Dictionary-Objekt dar. Dieser in Python bereits zur Verfügung gestellte Datentyp erlaubt uns, Schlüssel-Wert-Paare zu speichern und schnell darauf zuzugreifen. Für einen Knoten u wäre dann graph[u] die Liste seiner Nachbarn. Um einen Graphen in einer Datei abzuspeichern, verwende ich ein Format, das sich an den International Collegiate Programming Contest anlehnt.
Beispiel.
Hier ein Beispiel für einen ungerichteten Graphen:
5 6 a b c d e e a c d c b a c b d a b
In der ersten Zeile sehen Sie $n$ und $m$, die Zahl der Knoten und Kanten. In der folgenden Zeile sehen Sie $n$ Strings, und zwar die Namen der Knoten (Ihre Namen dürfen also keine Leerzeichen enthalten). In den folgenden $m$ Zeilen sehen Sie jeweils zwei positive natürliche Zahlen $u v$, was bedeutet, dass $\{u,v\}$ eine Kante ist. In Python wäre dieser Graph
{'a': ['e', 'c', 'b'], 'b': ['c', 'd', 'a'], 'c': ['d', 'b', 'a'], 'd': ['c', 'b'], 'e': ['a']}
Beispiel.
Hier ein Beispiel für einen gerichteten Graphen:
6 9 1 2 3 4 5 6 5 6 6 5 5 3 4 3 2 4 3 3 3 2 1 3 1 2
In einem gerichteten Graphen bedeutet die Zeile $u v$, dass $(u,v)$ eine Kante ist. Daher haben wir hier sowohl $5 6$ als auch $6 5$. Auch kann ein gerichteter Graph Selbstschleifen haben, wie hier die Kante $(3,3)$. In Python wäre dieser Graph durch zwei Dictionaries repräsentiert:
out_neighbors = {1: [3, 2], 2: [4], 3: [3, 2], 4: [3], 5: [6, 3], 6: [5]}
in_neighbors = {1: [], 2: [3, 1], 3: [5, 4, 3, 1], 4: [2], 5: [6], 6: [5]}
Der ICPC-Kodierung sieht man nicht an, ob es sich um einen gerichteten oder ungerichteten Graphen handelt. Dies muss das lesende Programm dann wissen. Wenn Sie selber Graphen erstellen und in das obige Format exportieren wollen, dann nutzen Sie gerne meinen Graph-Editor:
Im Moment kann der keine Selbstschleifen kreieren und tut sich schwer, Zweierzyklen (also $(u,v)$ und $(v,u)$) gut darzustellen.