Allgemeines zu Graphen

Graph: Ein Graph \(G = (V, E, c)\) besteht aus einer Knotenmenge \(V\), einer Kantenmenge \(E\) und einer Kostenfunktion \(c: E \rightarrow \mathbb {R}\). Ist der Graph ungerichtet bzw. gerichtet, so sind die Elemente von \(E\) der Form \(\{a, b\}\) bzw. \((a, b)\) mit \(a, b \in V\). Man legt \(n = |V|\) und \(m = |E|\) fest.

Graphen sind das Modellierungswerkzeug für Algorithmen (z. B. Straßennetzwerke, soziale Netzwerke, Zuordnungsprobleme usw.).

Pfad: Ein Pfad von \(v\) nach \(w\) in einem gerichteten Graph \(G = (V, E)\) ist eine Folge von Knoten \(v_0 v_1 \dotsc v_{k-1} v_k\) mit \(v_0 = v\), \(v_k = w\) und \(\forall _{i=0,\dotsc ,k-1}\; (v_i, v_{i+1}) \in E\).
Dabei heißt \(k\) die Länge des Pfades.

Speicherung und Darstellung von Graphen im Speicher

  • Adjazenzmatrix: \(n \times n\)-Matrix \((\lambda _{vw})\) mit \(\lambda _{vw} = 1\), falls \((v, w) \in E\) und \(\lambda _{vw} = 0\) sonst.
    Platzbedarf: \(\sim n^2\)

  • Knoten-Kanten-Inzidenzmatrix: \(n \times m\)-Matrix \((\lambda _{ve})\) mit \(\lambda _{ve} = -1\) und \(\lambda _{we} = +1\), falls \(e = (v, w) \in E\). Platzbedarf: \(\sim n \cdot m\)

  • Adjazenzlisten: Jeder Graph lässt sich darstellen durch

    • Liste der Knoten,

    • Liste der Kanten,

    • für jeden Knoten \(v\) eine Liste der Kanten \(e\) mit \(\source (e) = v\) (ausgehende Kanten) und

    • für jeden Knoten \(v\) eine Liste der Kanten \(e\) mit \(\target (e) = v\) (eingehende Kanten).

    Konkret erstellt man dann zwei Datenstrukturen Knoten und Kante mit

    • Knoten: Nummer = \(1, \dotsc , n\),  nächster Knoten in Liste 1),
      erste ausgehende Kante in Liste 3),  erste eingehende Kante in Liste 4) und

    • Kante: Nummer = \(1, \dotsc , m\),
      source: Verweis auf Quellknoten,  target: Verweis auf Zielknoten,
      jeweils ein Verweis auf nächste Kante in Liste 2), 3) und 4).

    Platzbedarf: \(\sim n + m\)

Tiefensuche (DFS) und Klassifizierung von Kanten

Problem (Bestimmung aller von einem Knoten erreichbaren Knoten):
Gegeben sei ein gerichteter Graph \(G = (V, E)\) sowie ein ausgezeichneter Knoten \(s \in V\).
Wie bestimmt man alle Knoten \(v\), die von \(s\) erreichbar sind (d. h. es existiert ein Pfad von \(s\) nach \(v\))? Die von \(s\) erreichbaren Knoten sind \(s\) und alle Knoten, die von Knoten \(u\) mit \((s, u) \in E\) erreichbar sind. 

DFS(u)                     Annahme: Erreichbar[] ist Boolesches Array
   Erreichbar[u] := true    mit Erreichbar[v] = false fuer alle v in V (zu Beginn)
   forall e = (u, w)
      if Erreichbar[w] = false
         DFS(w)

Satz: Nach Ausführung von DFS(s) gilt
1. \(\forall _{v \in V}\) Erreichbar[\(v\)] = true \(\;\Leftrightarrow \;\) es gibt ein Pfad von \(s\) nach \(v\),
2. Laufzeit ist \(\O (n + m)\) unter der Annahme, dass auf die Liste der adjazenten Knoten eines Knotens in \(\O (1)\) zugegriffen werden kann.

Beweis: 1. „\(\Rightarrow \)“: Man konstruiert für einen Knoten \(v\) mit Erreichbar[\(v\)] = true einen Pfad \(\pi _v\) von \(s\) nach \(v\) induktiv: \(\pi _s = s\) sowie \(\pi _v = \pi _w v\), wobei \(v \not = s\) ein Knoten ist, der besucht wurde, und \((w, v) \in E\) so gewählt ist, dass DFS(\(v\)) ausgehend von DFS(\(w\)) aufgerufen wurde.
„\(\Leftarrow \)“: Sei \(v_0 \dotsc v_k\), \(v_0 = s\), \(v_k = v\) ein Pfad von \(s\) nach \(v\). Induktiv kann man zeigen, dass DFS(\(v_i\)), \(i = 0, \dotsc , k\) aufgerufen wurde (somit wurden alle \(v_i\) besucht). \(i = 0\) ist trivial, denn der erste Aufruf ist DFS(\(s\)). Angenommen, DFS(\(v_i\)) wurde aufgerufen. Dann wird in diesem Aufruf die Kante \((v_i, v_{i+1})\) betrachtet. Entweder wurde \(v_{i+1}\) schon betrachtet (fertig) oder wird jetzt aufgerufen (fertig).
2. Jeder Knoten und jede Kante wird maximal \(1\) Mal angeschaut.   ƒ

DFS heißt Tiefensuche und teilt die Kanten eines Graphen in vier disjunkte Klassen ein:
\(E = T \;\dot {\cup }\; F \;\dot {\cup }\; B \;\dot {\cup }\; C\), wobei der Zeitpunkt betrachtet wird, wenn DFS eine Kante \(e = (v, w)\) betrachtet. Dabei wird vorausgesetzt, dass der Graph keine Schlingen enthält.

  • \(e \in T\) (tree, Baumkante), falls \(w\) noch nicht besucht,

  • \(e \in F\) (forward, Vorwärtskante), falls \(w\) schon besucht und \(v \rightarrow ^\ast _T w\) auf Baumkanten,

  • \(e \in B\) (backward, Rückwärtskante), falls \(w\) schon besucht und \(w \rightarrow ^\ast _T v\) auf Baumkanten,

  • \(e \in C\) (cross, Querkante), falls \(w\) schon besucht und weder \(v \rightarrow ^\ast _T w\) noch \(w \rightarrow ^\ast _T v\).

Man kann nun einen erweiterten DFS betrachten, der zusätzlich zu der Einordnung jeder Kante den Aufrufszeitpunkt von DFS(v) jedes Knotens \(v\) in dfsnum[v] und den Zeitpunkt, wann DFS(v) abgeschlossen wurde, in compnum[v] speichert. 

DFS(v)                                                          Globale Variablen:
   besucht[v] := true                                            besucht[], zu Beginn alles false
   count1++                                                     count1 := 0, count2 := 0
   dfsnum[v] := count1
                                                                Oberroutine:
    forall e = (v, w)                                           forall s in V
       if besucht[w] = false                                       if besucht[s] = false
          fuege e zu T hinzu                                          DFS(s)
          DFS(w)
       else if v $\rightarrow^\ast_T$ w
          fuege e zu F hinzu
       else if w $\rightarrow^\ast_T$ v
          fuege e zu B hinzu
       else
          fuege e zu C hinzu

    count2++
    compnum[v] := count2

Lemma:

  • \(E = T \;\dot {\cup }\; F \;\dot {\cup }\; B \;\dot {\cup }\; C\),

  • Die Menge \(T\) entspricht dem Aufrufwald der rekursiven Aufrufe.

  • \(v \rightarrow ^\ast _T w \;\Leftrightarrow \;\) dfsnum[\(v\)] \(\le \) dfsnum[\(w\)] \(\;\land \;\) compnum[\(v\)] \(\ge \) compnum[\(w\)]

  • Seien \(v, w, z \in V\) mit \(v \rightarrow ^\ast _T w\) und \((w, z) \in E\) mit \(v \nrightarrow ^\ast _T z\), dann gilt:
    dfsnum[\(z\)] \(<\) dfsnum[\(v\)],   \((w, z) \in B \cup C\),
    compnum[\(z\)] \(>\) compnum[\(v\)] \(\;\Leftrightarrow \; (w, z) \in B\),
    compnum[\(z\)] \(<\) compnum[\(v\)] \(\;\Leftrightarrow \; (w, z) \in C\).

  • \(\forall _{(v, w) \in E}\; (v, w) \in T \cup F \;\Leftrightarrow \;\) dfsnum[\(v\)] \(<\) dfsnum[\(w\)]

  • \(\forall _{(v, w) \in E}\; (v, w) \in B \;\Leftrightarrow \;\) dfsnum[\(v\)] \(>\) dfsnum[\(w\)] \(\;\land \;\) compnum[\(v\)] \(<\) compnum[\(w\)]

  • \(\forall _{(v, w) \in E}\; (v, w) \in C \;\Leftrightarrow \;\) dfsnum[\(v\)] \(>\) dfsnum[\(w\)] \(\;\land \;\) compnum[\(v\)] \(>\) compnum[\(w\)]

Folgerungen: Die Klassifizierung der Kanten aus \(E\) in \(T\)-/\(F\)-/\(B\)-/\(C\)-Kanten kann mittels
dfsnum/compnum effizient algorithmisch erfolgen.
\(G\) ist azyklisch (d. h. besitzt keine Zyklen, also Pfade mit demselben Anfangs- und Endpunkt) \(\;\Leftrightarrow \; \forall _{(v,w) \in E}\;\) compnum[\(v\)] \(>\) compnum[\(w\)] \(\;\Leftrightarrow \;\) es gibt keine \(B\)-Kanten.
In diesem Fall ist \(\num (v) = n + 1 \;-\) compnum[\(v\)] eine topologische Sortierung.

topologische Sortierung: Ein gerichteter Graph hat eine topologische Sortierung, falls die Knoten auf einer horizontalen Linie gemalt werden können, sodass alle Kanten nur von links nach rechts gehen. Formal ist eine Abbildung \(\num : V \rightarrow \{1, \dotsc , n\}\) eine topologische Sortierung des gerichteten Graphen \(G = (V, E)\) mit \(|V| = n\), falls \(\num (v) < \num (w)\) für alle \((v, w) \in E\).
Ein gerichteter Graph \(G\) hat eine topologische Sortierung genau dann, wenn \(G\) azyklisch ist.

Zusammenhangskomponenten

Zusammenhangskomponenten (ZHK) eines ungerichteten Graphen:
maximale Teilmenge \(V’ \subseteq V\), sodass für alle \(v, w \in V’\) ein Pfad von \(v\) nach \(w\) existiert.

starke Zusammenhangskomponenten (SZHK) eines gerichteten Graphen:
maximale Teilmenge \(V’ \subseteq V\), welche stark zusammenhängend ist.
Eine Knotenmenge \(V’ \subseteq V\) ist stark zusammenhängend, wenn es für alle \(v, w \in V’\) einen Pfad von \(v\) nach \(w\) gibt. \(v\) liegt in derselben SZHK wie \(w\) genau dann, wenn es einen Pfad von \(v\) nach \(w\) und einen Pfad von \(w\) nach \(v\) gibt.

Satz: Seien \((V_1, E_1), \dotsc , (V_k, E_k)\) die SZHKs von \(G\). Dann gilt:
1. \(\bigcup _{i=1}^k V_i = V\),     2. \(\forall _{i, j = 1, \dotsc , k,\; i \not = j}\; V_i \cap V_j = \emptyset \),
3. Der Graph \(G’ = (V’, E’)\) mit \(V’ = \{v_1, \dotsc , v_k\}\) (wobei \(v_i \in V_i\) für \(i = 1, \dotsc , k\)) und
\(E’ = \{(v_i, v_j) \;|\; \exists _{v \in V_i,\; w \in V_j}\; (v, w) \in E,\; i \not = j\}\) ist azyklisch (component graph).

naive Berechnung der SZHK eines Knotens \(v\): Rufe zunächst DFS(\(v\)) auf und speichere alle von \(v\) erreichbaren Knoten in \(R\). Rufe dann für alle \(w \in R\) DFS(\(w\)) auf. Falls \(v\) dabei erreicht wird, liegt \(w\) in derselben SZHK wie \(v\).

etwas effizientere Berechnung: Rufe zunächst wie eben DFS(\(v\)) auf und speichere alle von \(v\) erreichbaren Knoten in \(R\). Rufe dann DFS(\(v\)) auf \(G^{-1}\) auf (wobei \(G^{-1}\) dieselben Knoten und die gleichen, bloß umgedrehten Kanten wie \(G\) hat), speichere somit alle Knoten, von denen \(v\) erreichbar ist, in \(R’\). Die SZHK von \(v\) ist dann \(R \cap R’\).

Grundidee der effizienten Berechnung von SZHKs:
SZHKs bilden Teilbäume des von DFS (durch die \(T\)-Kanten) aufgespannten Baums \(\mathcal {T}\).

Beobachtung (Lemma): Wenn \(a \rightarrow ^\ast b\) und \(b \rightarrow ^\ast a\) gilt, dann liegen alle Knoten \(c\) „in der Mitte“, d. h. \(a \rightarrow ^\ast c \rightarrow ^\ast b\), in derselben SZHK wie \(a\) und \(b\).

Beweis: Angenommen, die SZHK \(\Sigma \) eines Knotens \(v\) liegt in zwei disjunkten Teilbäumen \(\Sigma _1, \Sigma _2\) von \(\mathcal {T}\). Entweder liegt ein Bereich „unterhalb“ eines anderen oder die beiden Bereiche liegen „nebeneinander“. Im ersten Fall würden die Knoten dazwischen aufgrund des Lemmas auch zur selben SZHK gehören wie die Knoten von \(\Sigma _1\) und \(\Sigma _2\) (Widerspruch). Im zweiten Fall gibt es für jeden Knoten \(v \in \Sigma _1\) einen Pfad zu allen Knoten \(w \in \Sigma _2\) und umgekehrt. Ohne Einschränkung wurde \(\Sigma _1\) vor \(\Sigma _2\) von DFS besucht. Dann hätte aber \(\Sigma _2\) von \(\Sigma _1\) aus besucht werden müssen, also würde \(\Sigma _2\) unterhalb von \(\Sigma _1\) im Baum stehen (Widerspruch).   ƒ

Kopf einer SZHK: Der Kopf einer SZHK ist der Knoten mit der kleinsten dfsnum.

Behauptung: Ein Knoten \(v\) ist Kopf seiner SZHK, wenn es aus dem Unterbaum unter \(v\) keine \(B\)-Kante zu einem Vorfahr von \(v\) gibt und es keine \(C\)-Kante aus dem Unterbaum unter \(v\) zu einem Knoten \(w\) gibt, dessen SZHK einen Kopf \(z\) hat, der Vorfahr von \(v\) ist.

Beweis: Angenommen, es gäbe eine \(B\)-Kante von einem Nachfolger von \(v\) zu einem Vorgänger von \(v\). Dann ist dieser Vorgänger in derselben SZHK und daher \(v\) nicht Kopf.
Angenommen, es gäbe eine \(C\)-Kante von einem Nachfolger von \(v\) zu \(w\) mit Kopf \(z\), wobei \(z\) ein Vorfahr von \(v\) ist. Dann liegt \(z\) in derselben SZHK wie \(v\) und daher ist \(v\) nicht Kopf. Ist \(z\) nicht Vorfahr von \(v\), dann kann \(z\) nicht in derselben SZHK wie \(v\) sein, denn sonst wäre die SZHK in zwei disjunkten Teilbäumen, daher können solche Kanten ignoriert werden.   ƒ

Es reicht also, für einen Knoten \(v\) zu entscheiden, ob es keine \(B\)-Kante aus einem Teilbaum unter \(v\) zu einem seiner Vorgänger und es keine \(C\)-Kante zu Knoten mit Köpfen, die Vorgänger von \(v\) sind, gibt. In diesem Fall ist \(v\) Kopf seiner SZHK.
Ein Knoten \(v\) heißt „fertig“, falls seine SZHK \([v]\) vollständig von DFS besucht wurde (alle Knoten und alle Kanten).
Man führt nun in DFS ein zusätzliches Feld lownum[] ein, welches die kleinste dfsnum eines aus dem Unterbaum von \(v\) durch eine \(B\)- oder \(C\)-Kante erreichbaren, unfertigen Knotens \(w\) speichert. Außerdem führt man einen Stack unfertig[] ein, welche die Knoten speichert, die nicht fertig sind.

Falls nun dfsnum[\(v\)] \(=\) lownum[\(v\)] gerade vor Abschluss der Bearbeitung von DFS(\(v\)) ist, so ist \(v\) Kopf von \([v]\) und alle Elemente im Stack unfertig[] sind die Knoten in \([v]\). Somit können die SZHKs in \(\O (n + m)\) berechnet werden. 

DFS(v)                                                        forall v in V
   besucht[v] := true                                            besucht[v] := false
   count1++                                                      fertig[v] := false
   dfsnum[v] := count1                                           count1 := 0
   lownum[v] := dfsnum[v]                                        DFS(v)
   unfertig.push(v)

   forall e = (v, w)
      if besucht[w] = false
         DFS(w)
         lownum[v] := min(lownum[v], lownum[w])
      else if fertig[w] = false
         lownum[v] := min(lownum[v], dfsnum[w])

   if lownum[v] = dfsnum[v]
      print "Komponente"
      do
         t := unfertig.pop()
         print t
         fertig[t] := true
      while t != v

Breitensuche (BFS)

Distanz zweier Knoten in gerichteten Graphen: Wie kann man für einen gegebenen Startknoten \(s\) für alle \(v \in V\) die Distanz \(d(v) := \min \{k \;|\; \exists \text {Pfad von } s \text { nach } v \text { mit } k \text { Knoten}\}\) berechnen?

Idee: Man bestimmt iterativ Mengen \(V_i = \{v \in V \;|\; d(v) = i\}\) durch
\(V_i = \{v \in (V \setminus \bigcup _{k < i} V_k) \;|\; \exists _{(w,v) \in E}\; w \in V_{i-1}\}\) für \(i \in \mathbb {N}\) (\(V_0 = \{s\}\)).

Beweis: 1. \(v \in V_i \;\Rightarrow \; d(v) \le i\) mit Induktion über \(i\): \(i = 0\) ist trivial, denn \(V_0 = \{s\}\) und \(d(s) = 0 \le 0\). Sei \(v \in V_i\). Dann gibt es ein \(w \in V_{i-1}\) mit \((w, v) \in E\).
Dann ist allerdings \(d(v) \le d(w) + 1 \le (i - 1) + 1 = i\).
2. \(d(v) = i \;\Rightarrow \; v \in V_0 \cup \dotsb \cup V_i\) mit Induktion über \(i\): \(i = 0\) ist trivial, denn \(d(v) = 0 \;\Rightarrow \; v = s\), \(v \in V_0\). Sei \(d(v) = i\). Dann gibt es ein \(u\) mit \((u, v) \in E\) und \(d(u) = i - 1\). Nach IV gilt \(u \in V_0 \cup \dotsb \cup V_{i-1}\), daher gilt \(v \in V_0 \cup \dotsb \cup V_{i-1} \cup V_i\).
3. \(v \in V_i \;\Rightarrow \; d(v) = i\), denn nach 1. gilt \(d(v) \le i\). Falls \(d(v) < i\) wäre, dann wäre nach 2. \(v \in V_0 \cup \dotsb \cup V_{i-1}\) und somit \(v \notin V_i\), da die \(V_i\) disjunkt sind.
4. \(d(v) = i \;\Rightarrow \; v \in V_i\) folgt direkt aus 2. wegen der Disjunktheit der \(V_i\).   ƒ

BFS arbeitet in Phasen und benutzt zwei Schlangen/Queues. Zu Beginn von Phase \(i\) gilt für die Knoten mit \(d(v) \le i\), dass dist[\(v\)] \(= d(v)\), für die Knoten mit \(d(v) > i\) gilt
dist[\(v\)] \(= \infty \) und current enthält die Menge \(V_i\) sowie next ist leer. 

current := {s}
next := {}
dist[s] := 0
forall v in V ohne {s}
   dist[v] := unendlich

while current != {} do
   while current != {} do
      v := current.pop()
      forall e = (v, w)
         if dist[w] = unendlich
            dist[w] := dist[v] + 1
            next.push(w)
   od
   current := next
   next := {}
od

Die Laufzeit von BFS ist \(\O (n + m)\), da jeder Knoten höchstens \(1\) Mal entfernt wird und dann alle seine ausgehenden Kanten betrachtet werden. Man hätte oben auch Listen, Stacks usw. benutzen können. Außerdem kann man das Programm so modifizieren, sodass nur eine Queue benutzt wird.

Kürzeste Wege in gewichteten Graphen

Berechnung kürzester Wege in gewichteten Graphen: Gegeben sei ein Graph
\(G = (V, E, c)\), wobei \(c: E \rightarrow \mathbb {R}\) die Kosten für jede Kante angibt, sowie ein Knoten \(s \in V\).
Zu bestimmen ist nun \(d(v) := \inf \{c(\pi ) \;|\; \pi \text { ist Pfad von } s \text { nach } v\}\) für alle Knoten \(v \in V\), wobei für einen Pfad \(\pi = v_0 \dotsc v_k\) gilt, dass \(c(\pi ) := \sum _{i=0}^{k-1} c(v_i, v_{i+1})\).

Durch einen negativen Zyklus kann es auch Knoten \(v\) mit \(d(v) = -\infty \) geben.

Eine naive Berechnung würde einfach alle Pfade von \(s\) nach \(v\) betrachten. Dies können allerdings je nach Graph sehr viele oder sogar unendlich viele sein.

Idee für einen Algorithmus: Man berechnet „vorläufige“ Distanzwerte dist[] und will erreichen, dass später dist[\(v\)] \(= d(v)\) für alle \(v \in V\) ist.
Dazu setzt man zu Beginn dist[\(s\)] \(= 0\) und dist[\(v\)] \(= +\infty \) für alle \(v \in V\) mit \(v \not = s\).
Solange es nun Kanten \(e = (v, w) \in E\) mit dist[\(w\)] \(>\) dist[\(v\)] \(+\; c(v,w)\) gibt, setze
dist[\(w\)] \(=\) dist[\(v\)] \(+\; c(v,w)\) (Kantenrelaxierung). Man zielt darauf ab, dass es später keine solche Kanten mehr gibt und dist[\(v\)] \(= d(v)\) für alle \(v \in V\).

Es kommt nun darauf an, in welcher Reihenfolge die Kanten betrachtet werden, damit möglichst wenig Kanten mehrfach betrachtet werden.

Invariante: \(U \subseteq V\) definiert durch \(v \notin U \;\Leftrightarrow \;\) \(\forall _{(v,w) \in E}\;\) dist[\(v\)] \(+\; c(v,w) \ge \) dist[\(w\)]
(\(U\) ist Menge der Knoten, die ausgehende Kanten haben, die noch betrachtet werden müssen). 

dist[s] = 0
forall v in V, v != s
   dist[v] = +unendlich
U = {s}

while U != {}
   entferne v in U (beliebig)
   forall e = (v,w)
      x = dist[v] + c(v, w)
      if (x <dist[w])
         dist[w] = x
         U = U \cup {w}

Eigenschaften des Algorithmus:
1. Invariante ist erfüllt.
2. Für den Fall dist[\(w\)] \(> d(w) > -\infty \) gibt es einen Knoten \(u\) auf dem kürzesten Weg von \(s\) nach \(w\) mit \(u \in U\) und dist[\(u\)] \(= d(u)\).
3. Wird ein Knoten \(u\) aus \(U\) zu einem Zeitpunkt mit dist[\(u\)] \(= d(u)\) entfernt, so wird \(u\) nie mehr in \(U\) aufgenommen.

Beweis:

  • Die Invariante gilt nach der Initialisierung. Solange \(u \notin U\) gilt, ändert sich dist[\(u\)] nicht, d. h. der Wert der linken Seite ändert sich nicht. Die rechte Seite wird im Verlauf des Algorithmus nur kleiner und wenn \(u\) aus \(U\) entfernt wird, wird die Gültigkeit der Invariante sichergestellt.

  • Seien \(v_0 v_1 \dotsc v_k\) (\(v_0 = s\), \(v_k = w\)) ein kürzester Weg von \(s\) nach \(w\) und \(i\) maximal mit dist[\(v_i\)] \(= d(v_i)\). \(i\) existiert, denn es gilt \(d(s) =\) dist[\(s\)] \(= 0\). Angenommen, es gilt \(v_i \notin U\). Dann ist dist[\(v_{i+1}\)] \(\le d(v_i) + c(v_i, v_{i+1})\) nach Definition von \(U\). Zusätzlich gilt n. V. dist[\(v_i\)] \(= d(v_i)\), daher ist dist[\(v_{i+1}\)] \(= d(v_{i+1})\) (\(v_0 \dotsc v_i v_{i+1} \dotsc w\) ist kürzester Weg, also ist auch \(v_0 \dotsc v_i v_{i+1}\) kürzester Weg). Widerspruch, da dann \(i\) nicht maximal.

  ƒ

Implementierung:

  • allgemeine Kantenkosten (auch negativ):
    Implementiere \(U\) als Schlange, entferne immer erstes Element aus \(U\).
    Wenn \(v\) zu \(U\) hinzugefügt wird (und es ist noch nicht in \(U\)), füge es hinten an.

    Behauptung: Wenn \(d(w) > -\infty \) für alle \(w \in V\) gilt, dann wird jeder Knoten höchstens \(n\)-mal aus \(U\) entfernt.

    Beweis: Betrachte \(U\), wenn \(v\) zu \(U\) hinzugefügt wird. \(U\) enthält laut 2. (siehe oben) einen Knoten \(z\) mit dist[\(z\)] \(= d(z)\). \(z\) wird vor \(v\) aus \(U\) entfernt und zwar endgültig (siehe 3.). Also kommt \(v\) maximal \(n-1\)-mal zu \(U\) hinzu. ƒ

    Laufzeit: Die Laufzeit ist \(\O (m \cdot n)\), da jede Kante maximal \(n\)-mal anschaut wird (nämlich jedes Mal, wenn ihr Quellknoten aus \(U\) entfernt wird).

  • \(G\) ist azyklisch:
    Sortiere \(G\) topologisch und gehe Knoten in aufsteigender Reihenfolge durch.

  • nicht-negative Kantenkosten (Algorithmus von Dijkstra):
    Entferne immer das Element aus \(U\) mit dem kleinsten dist-Wert.

    Behauptung: Sei \(w \in U\) mit dist[\(w\)] minimal. Dann ist dist[\(w\)] \(= d(w)\).

    Beweis: Falls dist[\(w\)] \(> d(w)\), existiert ein Knoten \(v\) auf kürzestem Weg von \(s\) nach \(w\) mit \(v \in U\) und dist[\(v\)] \(= d(v)\). Weil die Kantenkosten nicht-negativ sind, gilt daher \(d(v) \le d(w) <\) dist[\(w\)]. Also ist dist[\(v\)] \(<\) dist[\(w\)], ein Widerspruch, da \(w \in U\) mit dist[\(w\)] minimal. ƒ

    Laufzeit: Jeder Knoten wird maximal 1 Mal aus \(U\) entnommen. Jeder Knoten ändert maximal \(\indeg (v)\) Mal seine Distanz. Also gibt es maximal \(n\) Minimumsextraktionen und \(m\) Distanzänderungen. Wie findet man das Minimum der dist-Werte in \(U\)? Eine naive Bestimmung würde jedes Mal durch \(U\) laufen, dies kostet jedoch dann \(\O (n^2 + m)\). Besser ist es, per Heap die Minima zu bestimmen, dann ist die Laufzeit \(\O (n \cdot \log n + m \cdot \log n)\). Noch besser ist es, wenn man Fibonacci-Heaps oder R-Heaps nutzt.

Weitere Graphprobleme mit polynomiellen Algorithmus

Ein Beispiel für ein nicht-polynomielles Problem ist das stable-set/independent-set-Problem: Gegeben sei ein Graph \(G = (V, E)\). Finde \(S \subseteq V\), sodass es für alle \(u, v \in S\) keine Kante \((u, v) \in E\) gibt und \(S\) die größtmögliche Kardinalität hat.

Netwerkfluss: Gegeben seien \(G = (V, E)\) gerichtet, \(s, t \in V\) sowie \(\mycap : E \rightarrow \mathbb {R}_0^+\).
Gesucht ist \(f: E \rightarrow \mathbb {R}_0^+\), sodass
1.  für alle \(e \in E\) gilt, dass \(0 \le f(e) \le \mycap (e)\),
2.  für alle \(v \in V \setminus \{s, t\}\) gilt, dass \(\sum _{e = (v, \cdot ) \in E} f(e) = \sum _{e = (\cdot , v) \in E} f(e)\), sowie
3.  \(\sum _{e = (s, \cdot ) \in E} f(e)\) ist maximal.
Zusätzlich kann \(\cost : E \rightarrow \mathbb {R}\) gegeben sein. Dann wird der maximale Fluss bei minimalen Kosten gesucht.

Matching (Bipartit): Gegeben sei \(G = (A \cup B, E)\) ungerichtet, wobei \(A \cap B = \emptyset \) sowie \(E \subseteq A \times B\). Gesucht ist eine Menge \(M \subseteq E\) mit \(|M|\) maximal sowie für alle \(v \in A \cup B\) gibt es höchstens eine Kante inzident zu \(v\). \(M\) bezeichnet man als Matching. Zusätzlich kann es noch \(\cost : E \rightarrow \mathbb {R}\) geben, wobei dann ein Matching mit maximalen/minimalen Kosten gesucht ist.

Ein Matching-Problem lautet: \(A\) sind Männer, \(B\) sind Frauen und \(|A| = |B| = n\). Jeder Mann \(a \in A\) bzw. jede Frau \(b \in B\) hat eine totale Ordnung \(<_a\) der Frauen bzw. \(<_b\) der Männer. Gesucht ist ein „gutes“ Matching, d. h. Zuordnung Männer – Frauen.

\(M\) heißt instabil, falls es ein \(a \in A\) und ein \(b \in B\) gibt mit
1.  \((a, b) \notin M\),
2.  \(a\) zieht \(b\) seiner Partnerin \(M(a)\) vor, d. h. \(b >_a M(a)\), und
3.  \(b\) zieht \(a\) ihrem Partner \(M(b)\) vor, d. h. \(a >_b M(b)\).
\(M\) heißt stabil, falls \(M\) nicht instabil ist.

Es gibt immer ein stabiles Matching. Dieses kann mit folgendem Algorithmus bestimmt werden:

  • Jeder alleinstehende Mann macht oberster Frau auf seiner Liste einen Antrag.

  • Jede Frau sucht sich aus den Angeboten und dem aktuellen Partner den Besten aus und schickt die anderen weg.

  • Jeder abgewiesene Mann streicht oberste Frau von seiner Liste und wird (bzw. bleibt) alleinstehend. Das Verfahren wird so lange wiederholt, bis jeder Mann eine Frau hat.

Behauptung:
Der Algorithmus erzeugt ein stabiles Matching, welches für alle Männer optimal ist.

Beweis:

  • \(M\) ist vollständig (jeder Mann/jede Frau bekommt einen Partner).
    Falls eine Frau einen Partner hat, hat sie ab da immer einen. Falls am Ende Frau \(b\) keinen Partner hat, hat ein Mann \(a\) keine Partnerin. \(a\) hätte \(b\) irgendwann einmal gefragt und \(b\) wäre mit \(a\) zusammen (oder mit einem besseren), ein Widerspruch.

  • \(M\) ist stabil.
    Sei \((a, b’) \in M\), \(b \not = b’\) beliebige Frau. Falls der Mann \(a\) der Frau \(b\) einen Antrag gemacht hat und wg. \(a’ \not = a\) abgewiesen wurde, hat \(b\) einen Partner, den sie \(a\) vorzieht. Falls der Mann \(a\) der Frau \(b\) keinen Antrag gemacht hat, hat \(a\) eine Partnerin, die er \(b\) vorzieht.

  • \(M\) ist für alle Männer optimal, d. h. falls \(a\) von \(b\) zurückgewiesen wurde, dann ist \(b\) für \(a\) unerreichbar, d. h. es gibt kein stabiles Matching \(M^\ast \) mit \((a, b) \in M^\ast \).
    Der Beweis erfolgt mit Induktion über die Anzahl der Runden des Algorithmus. Die Induktionsbehauptung ist: Falls \(a\) von \(b\) in Runde \(\le i\) zurückgewiesen wurde, ist \(b\) für \(a\) unerreichbar.
    IA: \(i = 0\), klar, da niemand zurückgewiesen
    IS: Angenommen, \(a\) wird von \(b\) in der \(i\)-ten Runde zurückgewiesen. Dann hat \(b\) am Ende der Runde einen „besseren“ Partner \(a’\). Angenommen, es gäbe ein stabiles Matching \(M^\ast \) mit \((a, b) \in M^\ast \). \(a’\) kann in \(M^\ast \) nicht mit \(b\) zusammen sein.
    Fall 1: \(M^\ast (a’)\) steht vor \(b\) in der Reihenfolge von \(a’\). Da \(a’\) der Frau \(b\) schon einen Antrag gemacht hat, hat er \(M^\ast (a’)\) auch schon einen Antrag gemacht (in einer Runde davor) und wurde zurückgewiesen. Nach IV ist \(M^\ast (a’)\) für \(a’\) unerreichbar, ein Widerspruch, denn \(a’\) und \(M^\ast (a’)\) sind im stabilen Matching \(M^\ast \) zusammen (\((a’, M^\ast (a’)) \in M^\ast \)).
    Fall 2: \(M^\ast (a’)\) steht nach \(b\) in der Reihenfolge von \(a’\). Dann würde \(a’\) \(b\) bevorzugen und \(b\) würde \(a’\) bevorzugen, ein Widerspruch zu \((a, b) \in M^\ast \).