Netzwerke

Netzwerke sind spezialformen von Graphen mit bestimmten Eigenschaften.

Definition

Ein gewichteter Digraph G=(V,E,c)G = (V,E,c) heißt Netzwerk, wenn er eine Quelle s∈Vs \in V und eine Senke t∈Vt \in V besitzt und jede Kante e∈Ee \in E eine Kapazität c:E→R+c: E \rightarrow \mathbb{R}_{+} hat.

Beispiel

Das Beispiel zeigt ein Netzwerk mit Quelle ss und Senke tt.

Definition

Sei G(V,E,c)G(V,E,c) ein Netzwerk. Dann heißt σ−(v):={(u,v)∈E}\sigma^{-}(v) := \{(u,v) \in E\} die Menge der eingehenden Kanten in vv und σ+(v):={(v,u)∈E}\sigma^{+}(v) := \{(v,u) \in E\} die Menge der ausgehenden Kanten.

Beispiel

Für das gegebene Netzwerk ist σ−(a):={(s,a),(c,a)}\sigma^{-}(a) := \{(s,a), (c,a)\} und σ+(a):={(a,b)}\sigma^{+}(a) := \{(a,b)\}.

Flüsse

Als Fluss bezeichene wir die Einheiten die entlang der Kanten eines Netzweks geschickt werden.

Definition

In einem Netzwerk G=(V,E,c)G=(V, E, c) heißt ein Funktion f:E→R+f:E \rightarrow \mathbb{R}_{+} ein zulässiger Fluss, wenn sie folgende Eigenschaften erfüllt:

  • Flusserhaltungbedingung: ∑e∈σ−(v)f(e)=∑e∈σ+(v)f(e),∀v∈V{s,t}\sum_{e \in \sigma^{-}(v)} f(e) = \sum_{e \in \sigma^{+}(v)} f(e), \forall v \in V \\ \{s,t\}
  • Kapazitätsbedingung: 0≤f(e)≤c(e),∀e∈E0 \leq f(e) \leq c(e), \forall e \in E

Beispiel

Wir schreiben den Fluss einer Kante links vom / und die Kapazität rechts. Die Kante (s,a)(s,a) hat also den Fluss 11 und die Kapazität 16.

Überschuss

Definition

Gegeben sei ein Netzwerk G=(V,E,c)G = (V,E,c) mit Quelle s∈Vs \in V und Fluss ff.
Dann heißt exf(v):=∑e∈σ+(v)f(e)−∑e∈σ−(v)f(e)ex_f(v) := \sum_{e \in \sigma^{+}(v)} f(e) - \sum_{e \in \sigma^{-}(v)} f(e) der Überschuss eines Knotens v∈Vv \in V.
Dazu heißt val(f)=exf(s)val(f) = ex_f(s) Flusswert.

Aus der Flusserhaltungbedingung folgen zwei Eigenschaften für Überschüsse:

  • exf(s)=−exf(t)ex_f(s) = -ex_f(t)
  • exf(v)=0ex_f(v) = 0 für alle Knoten v≠s,tv \neq s,t

Residualgraph

Ein Residualgraph zu einem Netzwerk mit gegebenen Fluss zeigt uns wie der Fluss verändert werden kann.

Definition

Für ein Netzwerk G=(V,E,c)G=(V,E,c) mit Fluss ff heißt Gf=(V,Ef,cf)G_f = (V, E_f, c_f) Residualgraph mit:

  • Ef={(a,b)∈V×V:cf(a,b)>0}E_f = \{(a,b) \in V \times V : c_f(a,b) > 0\}
  • cf={c(a,b)−f(a,b)falls (a,b)∈E (Vorwa¨rtskante),f(b,a)falls (b,a)∈E (Ru¨ckwa¨rtskante).c_f = \begin{cases} c(a,b) - f(a,b) & \text{falls } (a,b) \in E \text{ (Vorwärtskante)}, \\ f(b,a) & \text{falls } (b,a) \in E \text{ (Rückwärtskante)}.\end{cases}

Als Vorwärtskante bezeichen wir eine Kante e∈Efe \in E_f, die genau so auch im Netzwerk GG vorkommt, also e∈Ee \in E.
Dem entsprechend nennen wir eine Kante e∈Efe \in E_f Rückwärtskante|rueckwaertskante, wenn das Komplement von ee im Netzwerk GG vorkommt, also e‾∈E\overline{e} \in E. Eine Kante (b,a)∈Ef(b,a) \in E_f heißt also Rückwärtskante|rueckwaertskante, wenn (a,b)∈E(a,b) \in E.

Beispiel

In diesem Beispiel sehen wir eine Netzwerk GG mit Fluss ff. Dadrunter ist der dazugehörige Residualgraph GfG_f.

Netzwerk G=(V,E,c)G = (V,E,c):

  • In diesem Beispiel werden wir Schritt für Schritt den Residualgraphen GfG_f zum Netzwerk GG besimmen. Dabei werden die Vorwärtskanten in GfG_f als durchgezogene Pfeile dargestellt und die Rückwärtskanten|rueckwaertskante gestrichelt.

  • Als Erstes werden wir die etsprechende Vorwärtskante zur Kante (s,a)∈E(s,a) \in E bestimmen. Wir erhalten dazu eine neue Kante (s,a)∈Ef(s,a) \in E_f mit der dazugehörigen Residualkapazität: cf(s,a)=c(s,a)−f(s,a)=15−9=6c_f(s,a) = c(s,a) - f(s,a) = 15 - 9 = 6

Kanten mit einer Residualkapazität von 0 könnnen weggelassen werden, wie hier die Kanten (a,b),(d,b)(a,b), (d,b) und (d,t)(d,t). Im Residualgraph sind die Vorwärtskanten die Kanten, die die Ausrichtung haben wie die Kanten im Ursprungsnetzwerk. Die Rückwärtskanten|rueckwaertskante sind hier gestrichelt dargestellt und gehen entgegen der Ausrichtung der Kanten im Ursprungsnetzwerk.

f-augmentierende Wege

Als ff-augmentierende Wege bezeichen wir die Wege vom Knoten ss nach tt in GfG_f, andenhnen der Fluss in GG Augmentiert werden kann.

Definition

Sei GG ein gewichteter Digraph mit dazugehörigem Residualgraph GfG_f. Dann heißt ein Weg PP von ss nach tt in GG ff-augmentierend, wenn P⊆EfP \subseteq E_f.

Bottleneck-Kapazität

Definition

Sei PP ein ff-augmentierender Weg in GG. Dann heißt γ\gamma die Bottleneck-Kapazität von PP mit γ=min⁡e∈Pcf(e)\gamma = \min_{e \in P} c_f(e).

Die Bottleneck-Kapazität eines Weges PP ist also die kleinste Kapazität von allen Kanten in PP.

Augmentieren eines Flusses

Definition

Der Fluss ff in einem Netzwerk GG kann entlag eines ff-augmentierenden Weges wie folgt augmentiert werden:

f′(e):={f(e)+γfalls e∈P und e ist Vorwa¨rtskante,f(e)−γfalls e∈P und e ist Ru¨ckwa¨rtskante,f(e)sonst.f'(e) := \begin{cases} f(e) + \gamma & \text{falls } e \in P \text{ und $e$ ist Vorwärtskante}, \\ f(e) - \gamma & \text{falls } e \in P \text{ und $e$ ist Rückwärtskante}, \\ f(e) & \text{sonst}. \end{cases}

Der augmentierte Fluss ist dann f′f'.

Beispiel

  • In diesem Beispiel zeigen wir, wie der Fluss ff im Netzwerk GG augmentiert werden kann. Dafür sind hier zwei Graphen gegeben. Der obere ist das Netzwerk GG und darunter ist der zu GG gehörende Residualgraph GfG_f. Im Residualgraph sind die Vorwärtskanten wieder durchgezogen und die Rückwärskanten gestrichelt.

  • In GfG_f finden wir den ff-augmentierenden Weg P={(s,b),(b,a),(a,t)}P=\{(s,b), (b,a), (a,t)\}. Hier in lachsfarbend dargestellt. Wir können auch sehn, dass PP der einzige ff-augmentierende Weg in GfG_f ist, da es keinen anderen Weg in GfG_f von ss nach tt gibt.