Anki Deck Changes

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: %G>AD-xqw@

added

Note did not exist

New Note

Front

Sei $N = (V, A, c, s, t)$ ein Netzwerk ohne entgegen gerichtete Kanten und $f$ ein Fluss in $N$. Das Restnetzwerk $N_f := (V, A_f, r_f, s, t)$ ist definiert durch:

Ist $e \in A$ mit $f(e) < c(e)$, dann ist $e$ eine Kante in $A_f$ mit $r_f(e) := c(e) - f(e)$.
Ist $e \in A$ mit $f(e) > 0$, dann ist $e^{\mathrm{opp}}$ in $A_f$ mit $r_f(e^{\mathrm{opp}}) := f(e)$.
$A_f$ enthält nur Kanten wie in (1) und (2).

Den Wert $r_f(e)$ nennen wir die Restkapazität der Kante $e$.

Back

Sei $N = (V, A, c, s, t)$ ein Netzwerk ohne entgegen gerichtete Kanten und $f$ ein Fluss in $N$. Das Restnetzwerk $N_f := (V, A_f, r_f, s, t)$ ist definiert durch:

Ist $e \in A$ mit $f(e) < c(e)$, dann ist $e$ eine Kante in $A_f$ mit $r_f(e) := c(e) - f(e)$.
Ist $e \in A$ mit $f(e) > 0$, dann ist $e^{\mathrm{opp}}$ in $A_f$ mit $r_f(e^{\mathrm{opp}}) := f(e)$.
$A_f$ enthält nur Kanten wie in (1) und (2).

Den Wert $r_f(e)$ nennen wir die Restkapazität der Kante $e$.

Die Annahme „ohne entgegen gerichtete Kanten“ ist nur eine Vereinfachung, nicht essentiell. Sie sorgt dafür, dass $e$ und $e^{\mathrm{opp}}$ eindeutig auseinanderzuhalten sind.

Field-by-field Comparison

Field	Before	After
Text		Sei $N = (V, A, c, s, t)$ ein Netzwerk ohne entgegen gerichtete Kanten und $f$ ein Fluss in $N$. Das <b>Restnetzwerk</b> $N_f := (V, A_f, r_f, s, t)$ ist definiert durch:<ol><li>Ist $e \in A$ mit ${{c1::f(e) < c(e)}}$, dann ist $e$ eine Kante in $A_f$ mit $r_f(e) := {{c2::c(e) - f(e)}}$.</li><li>Ist $e \in A$ mit ${{c3::f(e) > 0}}$, dann ist $e^{\mathrm{opp}}$ in $A_f$ mit $r_f(e^{\mathrm{opp}}) := {{c4::f(e)}}$.</li><li>$A_f$ enthält {{c5::nur Kanten wie in (1) und (2)}}.</li></ol>Den Wert $r_f(e)$ nennen wir die <b>Restkapazität</b> der Kante $e$.
Extra		Die Annahme „ohne entgegen gerichtete Kanten“ ist nur eine Vereinfachung, nicht essentiell. Sie sorgt dafür, dass $e$ und $e^{\mathrm{opp}}$ eindeutig auseinanderzuhalten sind.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 2: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: (K=3:%@wQn

added

Note did not exist

New Note

Front

Die Kapazität eines s-t-Schnitts $(S, T)$ ist\[\operatorname{cap}(S, T) := {{c1::\sum_{(u, w) \in (S \times T) \cap A} c(u, w)}}.\]Wichtig: Die Kapazität ignoriert die Kanten von $T$ nach $S$.

Back

Nur Kanten, die von $S$ nach $T$ zeigen, zählen. Rückwärtskanten von $T$ nach $S$ tragen nicht zur Kapazität bei.

Field-by-field Comparison

Field	Before	After
Text		Die <b>Kapazität</b> eines s-t-Schnitts $(S, T)$ ist\[\operatorname{cap}(S, T) := {{c1::\sum_{(u, w) \in (S \times T) \cap A} c(u, w)}}.\]<b>Wichtig:</b> Die Kapazität {{c2::ignoriert die Kanten von $T$ nach $S$}}.
Extra		Nur Kanten, die von $S$ nach $T$ zeigen, zählen. Rückwärtskanten von $T$ nach $S$ tragen <b>nicht</b> zur Kapazität bei.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 3: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: +)94&7{KH`

added

Note did not exist

New Note

Front

Beweis von „kein Pfad in $N_f$ $\Rightarrow$ $\exists$ Schnitt $(S, T)$ mit $\operatorname{cap}(S, T) = \operatorname{val}(f)$“. Definiere\[\begin{gathered}S := {{c1::\{v \in V : v \text{ ist von } s \text{ in } N_f \text{ erreichbar}\}}}, \\T := V \setminus S.\end{gathered}\]Da kein s-t-Pfad in $N_f$ existiert, gilt $t \in T$, also ist $(S, T)$ ein s-t-Schnitt. Für jede Kante $(u, w) \in S \times T$ im Originalnetzwerk gilt $f(u, w) = c(u, w)$ (sonst wäre $w$ erreichbar), und für $(w, u) \in T \times S$ gilt $f(w, u) = 0$ (sonst gäbe es $(u, w)^{\mathrm{opp}}$ im Restnetzwerk). Damit $\operatorname{val}(f) = f(S, T) - f(T, S) = \operatorname{cap}(S, T) - 0$.

Back

Die zwei Bedingungen geben gleichzeitig die untere und die obere Schranke aus dem schwachen Dualitätslemma scharf: alle vorwärtsführenden Kanten sind saturiert, alle rückwärtsführenden Kanten tragen keinen Fluss.

Field-by-field Comparison

Field	Before	After
Text		<b>Beweis von „kein Pfad in $N_f$ $\Rightarrow$ $\exists$ Schnitt $(S, T)$ mit $\operatorname{cap}(S, T) = \operatorname{val}(f)$“.</b> Definiere\[\begin{gathered}S := {{c1::\{v \in V : v \text{ ist von } s \text{ in } N_f \text{ erreichbar}\}}}, \\T := V \setminus S.\end{gathered}\]Da kein s-t-Pfad in $N_f$ existiert, gilt {{c2::$t \in T$}}, also ist $(S, T)$ ein s-t-Schnitt. Für jede Kante $(u, w) \in S \times T$ im Originalnetzwerk gilt {{c3::$f(u, w) = c(u, w)$}} (sonst wäre $w$ erreichbar), und für $(w, u) \in T \times S$ gilt {{c4::$f(w, u) = 0$}} (sonst gäbe es $(u, w)^{\mathrm{opp}}$ im Restnetzwerk). Damit $\operatorname{val}(f) = f(S, T) - f(T, S) = \operatorname{cap}(S, T) - 0$.
Extra		Die zwei Bedingungen geben gleichzeitig die untere und die obere Schranke aus dem schwachen Dualitätslemma scharf: alle vorwärtsführenden Kanten sind saturiert, alle rückwärtsführenden Kanten tragen keinen Fluss.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 4: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 22W;$5Fvyk

added

Note did not exist

New Note

Front

Sei $N = (V, A, c, s, t)$ ein Netzwerk mit $c : A \to \mathbb{N}_0$, $n := |V|$, $m := |A|$, $U := \max_{e \in A} c(e)$. Dann gilt\[\operatorname{val}(f) \;\leq\; \operatorname{cap}(\{s\}, V \setminus \{s\}) \;\leq\; (n - 1)\,U,\]und der Ford-Fulkerson-Algorithmus benötigt höchstens $(n - 1)\,U$ Augmentierungsschritte.

Back

Der triviale Schnitt $(\{s\}, V \setminus \{s\})$ hat höchstens $n - 1$ ausgehende Kanten, jede mit Kapazität $\leq U$. Da jeder Augmentierungsschritt den Fluss um mindestens $1$ erhöht, ist $(n - 1)\,U$ auch eine obere Schranke für die Anzahl der Schritte.

Field-by-field Comparison

Field	Before	After
Text		Sei $N = (V, A, c, s, t)$ ein Netzwerk mit $c : A \to \mathbb{N}_0$, $n := \|V\|$, $m := \|A\|$, $U := \max_{e \in A} c(e)$. Dann gilt\[\operatorname{val}(f) \;\leq\; \operatorname{cap}(\{s\}, V \setminus \{s\}) \;\leq\; {{c1::(n - 1)\,U}},\]und der Ford-Fulkerson-Algorithmus benötigt höchstens {{c2::$(n - 1)\,U$}} Augmentierungsschritte.
Extra		Der triviale Schnitt $(\{s\}, V \setminus \{s\})$ hat höchstens $n - 1$ ausgehende Kanten, jede mit Kapazität $\leq U$. Da jeder Augmentierungsschritt den Fluss um mindestens $1$ erhöht, ist $(n - 1)\,U$ auch eine obere Schranke für die Anzahl der Schritte.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 5: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 2n$+!t=cpX

added

Note did not exist

New Note

Front

Maxflow-Mincut-Theorem. Jedes Netzwerk $N = (V, A, c, s, t)$ erfüllt\[{{c1::\max_{f \text{ Fluss} } \operatorname{val}(f) \;=\; \min_{(S,T) \text{ s-t-Schnitt} } \operatorname{cap}(S, T)}}.\]

Back

Maxflow-Mincut-Theorem. Jedes Netzwerk $N = (V, A, c, s, t)$ erfüllt\[{{c1::\max_{f \text{ Fluss} } \operatorname{val}(f) \;=\; \min_{(S,T) \text{ s-t-Schnitt} } \operatorname{cap}(S, T)}}.\]

Aus dem Theorem folgt: ein einfaches Maximalitätszertifikat (in Form eines passenden Schnitts) existiert immer.

Field-by-field Comparison

Field	Before	After
Text		<b>Maxflow-Mincut-Theorem.</b> Jedes Netzwerk $N = (V, A, c, s, t)$ erfüllt\[{{c1::\max_{f \text{ Fluss} } \operatorname{val}(f) \;=\; \min_{(S,T) \text{ s-t-Schnitt} } \operatorname{cap}(S, T)}}.\]
Extra		Aus dem Theorem folgt: ein einfaches Maximalitätszertifikat (in Form eines passenden Schnitts) existiert <b>immer</b>.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 6: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 8Hvimvm2ui

added

Note did not exist

New Note

Front

Für eine Partition $(U, W)$ von $V$ sei $f(U, W) := \sum_{(u, w) \in (U \times W) \cap A} f(u, w)$. Im Beweis von $\operatorname{val}(f) \leq \operatorname{cap}(S, T)$ zeigt man:\[\begin{gathered}\operatorname{val}(f) \;\overset{(\text{i})}{=}\; f(S, T) - f(T, S) \\\overset{(\text{ii})}{\leq}\; f(S, T) \\\overset{(\text{iii})}{\leq}\; \operatorname{cap}(S, T)\end{gathered}\]

Back

(i) Aufsummieren der Flusserhaltung über alle $v \in S$ (mit $s \in S$) und Ausnutzung der Definition $\operatorname{val}(f) = \operatorname{netoutflow}(s)$.
(ii) $f(T, S) \geq 0$, da $f \geq 0$ auf jeder Kante.
(iii) $f(u, w) \leq c(u, w)$ für jede Kante (Zulässigkeit).

Field-by-field Comparison

Field	Before	After
Text		Für eine Partition $(U, W)$ von $V$ sei $f(U, W) := \sum_{(u, w) \in (U \times W) \cap A} f(u, w)$. Im Beweis von $\operatorname{val}(f) \leq \operatorname{cap}(S, T)$ zeigt man:\[\begin{gathered}\operatorname{val}(f) \;\overset{(\text{i})}{=}\; {{c1::f(S, T) - f(T, S)}} \\\overset{(\text{ii})}{\leq}\; {{c2::f(S, T)}} \\\overset{(\text{iii})}{\leq}\; \operatorname{cap}(S, T)\end{gathered}\]
Extra		<ul><li>(i) Aufsummieren der Flusserhaltung über alle $v \in S$ (mit $s \in S$) und Ausnutzung der Definition $\operatorname{val}(f) = \operatorname{netoutflow}(s)$.</li><li>(ii) $f(T, S) \geq 0$, da $f \geq 0$ auf jeder Kante.</li><li>(iii) $f(u, w) \leq c(u, w)$ für jede Kante (Zulässigkeit).</li></ul>

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 7: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: 8gOogA]eP.

added

Note did not exist

New Note

Front

Satz (Ford-Fulkerson mit ganzzahligen Kapazitäten). Sei $N = (V, A, c, s, t)$ ein Netzwerk mit $c : A \to \mathbb{N}_0^{\leq U}$ (für $U \in \mathbb{N}$), ohne entgegen gerichtete Kanten. Dann:

Es gibt einen ganzzahligen maximalen Fluss.
Er kann in Zeit {{c2::$\mathcal{O}(m\,n\,U)$}} berechnet werden.

Back

Es gibt einen ganzzahligen maximalen Fluss.
Er kann in Zeit {{c2::$\mathcal{O}(m\,n\,U)$}} berechnet werden.

Begründung der Laufzeit: höchstens $(n-1)U = \mathcal{O}(nU)$ Augmentierungsschritte, jeder Schritt (Pfadsuche per BFS/DFS in $N_f$, Augmentierung, Update) braucht $\mathcal{O}(m)$ Zeit. Die Ganzzahligkeit folgt induktiv: Start mit $f \equiv 0$, und jeder Schritt erhält die Ganzzahligkeit, da $\varepsilon = \min_i \varepsilon_i$ ganzzahlig ist.

Field-by-field Comparison

Field	Before	After
Text		<b>Satz (Ford-Fulkerson mit ganzzahligen Kapazitäten).</b> Sei $N = (V, A, c, s, t)$ ein Netzwerk mit $c : A \to \mathbb{N}_0^{\leq U}$ (für $U \in \mathbb{N}$), ohne entgegen gerichtete Kanten. Dann:<ul><li>{{c1::Es gibt einen ganzzahligen maximalen Fluss}}.</li><li>Er kann in Zeit {{c2::$\mathcal{O}(m\,n\,U)$}} berechnet werden.</li></ul>
Extra		Begründung der Laufzeit: höchstens $(n-1)U = \mathcal{O}(nU)$ Augmentierungsschritte, jeder Schritt (Pfadsuche per BFS/DFS in $N_f$, Augmentierung, Update) braucht $\mathcal{O}(m)$ Zeit. Die Ganzzahligkeit folgt induktiv: Start mit $f \equiv 0$, und jeder Schritt erhält die Ganzzahligkeit, da $\varepsilon = \min_i \varepsilon_i$ ganzzahlig ist.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 8: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: CGEfL@^`C|

added

Note did not exist

New Note

Front

An einem inneren Knoten gibt es vier lokale Veränderungen des Flusses, die die Flusserhaltung erhalten. Zu beachten sind dabei:

bei $\mathbf{+\delta}$: die Kapazität der Kante
bei $\mathbf{-\delta}$: der aktuelle Fluss auf der Kante

Back

An einem inneren Knoten gibt es vier lokale Veränderungen des Flusses, die die Flusserhaltung erhalten. Zu beachten sind dabei:

bei $\mathbf{+\delta}$: die Kapazität der Kante
bei $\mathbf{-\delta}$: der aktuelle Fluss auf der Kante

Die vier Typen entstehen aus den Kombinationen $(+\delta\text{ rein}, +\delta\text{ raus})$, $(-\delta\text{ rein}, +\delta\text{ raus})$, $(+\delta\text{ raus}, -\delta\text{ rein})$, $(-\delta\text{ raus}, -\delta\text{ rein})$. Die Bilanz an jedem inneren Knoten bleibt unverändert.

Field-by-field Comparison

Field	Before	After
Text		An einem inneren Knoten gibt es vier lokale Veränderungen des Flusses, die die Flusserhaltung erhalten. Zu beachten sind dabei:<ul><li>bei $\mathbf{+\delta}$: {{c1::die Kapazität}} der Kante</li><li>bei $\mathbf{-\delta}$: {{c2::der aktuelle Fluss}} auf der Kante</li></ul>
Extra		Die vier Typen entstehen aus den Kombinationen $(+\delta\text{ rein}, +\delta\text{ raus})$, $(-\delta\text{ rein}, +\delta\text{ raus})$, $(+\delta\text{ raus}, -\delta\text{ rein})$, $(-\delta\text{ raus}, -\delta\text{ rein})$. Die Bilanz an jedem inneren Knoten bleibt unverändert.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 9: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: KyltqkDci3

added

Note did not exist

New Note

Front

Der Wert eines Flusses $f$ ist definiert als der Nettoabfluss der Quelle:\[\operatorname{val}(f) := \operatorname{netoutflow}(s) := {{c2::\sum_{u \in V : (s,u) \in A} f(s, u) \;-\; \sum_{u \in V : (u,s) \in A} f(u, s)}}.\]

Back

Eingehende Kanten an der Quelle werden abgezogen.

Field-by-field Comparison

Field	Before	After
Text		Der <b>Wert</b> eines Flusses $f$ ist definiert als der {{c1::Nettoabfluss der Quelle}}:\[\operatorname{val}(f) := \operatorname{netoutflow}(s) := {{c2::\sum_{u \in V : (s,u) \in A} f(s, u) \;-\; \sum_{u \in V : (u,s) \in A} f(u, s)}}.\]
Extra		Eingehende Kanten an der Quelle werden abgezogen.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 10: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: L%pGeRiAOW

added

Note did not exist

New Note

Front

MaxFlow-Problem. Gegeben ein Netzwerk $N = (V, A, c, s, t)$, finde einen Fluss $f$ grössten Werts (einen maximalen Fluss).

Back

MaxFlow-Problem. Gegeben ein Netzwerk $N = (V, A, c, s, t)$, finde einen Fluss $f$ grössten Werts (einen maximalen Fluss).

Der Wert eines Flusses wird über den Nettoabfluss der Quelle gemessen.

Field-by-field Comparison

Field	Before	After
Text		<b>MaxFlow-Problem.</b> Gegeben ein {{c1::Netzwerk $N = (V, A, c, s, t)$}}, finde einen {{c2::Fluss $f$ grössten Werts (einen <i>maximalen</i> Fluss)}}.
Extra		Der Wert eines Flusses wird über den Nettoabfluss der Quelle gemessen.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 11: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: MzalTh[qH4

added

Note did not exist

New Note

Front

Ein s-t-Schnitt für ein Netzwerk $(V, A, c, s, t)$ ist eine Partition $(S, T)$ von $V$ mit $s \in S$ und $t \in T$.

Back

Ein s-t-Schnitt für ein Netzwerk $(V, A, c, s, t)$ ist eine Partition $(S, T)$ von $V$ mit $s \in S$ und $t \in T$.

Also: $S \cup T = V$, $S \cap T = \emptyset$, Quelle in $S$, Senke in $T$.

Field-by-field Comparison

Field	Before	After
Text		Ein <b>s-t-Schnitt</b> für ein Netzwerk $(V, A, c, s, t)$ ist {{c1::eine Partition $(S, T)$ von $V$ mit $s \in S$ und $t \in T$}}.
Extra		Also: $S \cup T = V$, $S \cap T = \emptyset$, Quelle in $S$, Senke in $T$.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 12: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Q+Zm;1EOur

added

Note did not exist

New Note

Front

Ein Netzwerk ist ein Tupel $N = (V, A, c, s, t)$, wobei:

$(V, A)$ ist ein gerichteter Graph (ohne Schleifen),
$s \in V$ ist die Quelle,
$t \in V \setminus \{s\}$ ist die Senke,
$c : A \to \mathbb{R}_0^+$ ist die Kapazitätsfunktion.

Back

Ein Netzwerk ist ein Tupel $N = (V, A, c, s, t)$, wobei:

$(V, A)$ ist ein gerichteter Graph (ohne Schleifen),
$s \in V$ ist die Quelle,
$t \in V \setminus \{s\}$ ist die Senke,
$c : A \to \mathbb{R}_0^+$ ist die Kapazitätsfunktion.

Quelle und Senke müssen verschieden sein. Kapazitäten sind nichtnegativ reell.

Field-by-field Comparison

Field	Before	After
Text		Ein <b>Netzwerk</b> ist ein Tupel $N = (V, A, c, s, t)$, wobei:<ul><li>$(V, A)$ ist {{c1::ein gerichteter Graph (ohne Schleifen)}},</li><li>$s \in V$ ist {{c2::die <i>Quelle</i>}},</li><li>$t \in V \setminus \{s\}$ ist {{c3::die <i>Senke</i>}},</li><li>$c : A \to \mathbb{R}_0^+$ ist {{c4::die <i>Kapazitätsfunktion</i>}}.</li></ul>
Extra		Quelle und Senke müssen verschieden sein. Kapazitäten sind nichtnegativ reell.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 13: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: QqNbZ._RGi

added

Note did not exist

New Note

Front

Drei Fälle für eine Kante mit Kapazität $c$ und Fluss $f$ im Restnetzwerk:

Fluss $f$	Vorwärtskante $e$	Rückwärtskante $e^{\mathrm{opp}}$
$0 < f < c$	existiert mit $r_f(e) = c - f$	existiert mit $r_f(e^{\mathrm{opp) = f$}}
$f = c$ (saturiert)	existiert nicht	existiert mit $r_f(e^{\mathrm{opp) = c$}}
$f = 0$	existiert mit $r_f(e) = c$	existiert nicht

Back

Drei Fälle für eine Kante mit Kapazität $c$ und Fluss $f$ im Restnetzwerk:

Fluss $f$	Vorwärtskante $e$	Rückwärtskante $e^{\mathrm{opp}}$
$0 < f < c$	existiert mit $r_f(e) = c - f$	existiert mit $r_f(e^{\mathrm{opp) = f$}}
$f = c$ (saturiert)	existiert nicht	existiert mit $r_f(e^{\mathrm{opp) = c$}}
$f = 0$	existiert mit $r_f(e) = c$	existiert nicht

Saturierte Kanten produzieren nur die Rückwärtskante, leere Kanten nur die Vorwärtskante. Dazwischen entsteht ein „Doppelpfeil“ mit beiden Restkapazitäten.

Field-by-field Comparison

Field	Before	After
Text		Drei Fälle für eine Kante mit Kapazität $c$ und Fluss $f$ im Restnetzwerk:<table border="1" cellpadding="6" style="border-collapse:collapse"><tr><th>Fluss $f$</th><th>Vorwärtskante $e$</th><th>Rückwärtskante $e^{\mathrm{opp}}$</th></tr><tr><td>$0 < f < c$</td><td>{{c1::existiert mit $r_f(e) = c - f$}}</td><td>{{c2::existiert mit $r_f(e^{\mathrm{opp}}) = f$}}</td></tr><tr><td>$f = c$ (saturiert)</td><td>{{c3::existiert nicht}}</td><td>{{c4::existiert mit $r_f(e^{\mathrm{opp}}) = c$}}</td></tr><tr><td>$f = 0$</td><td>{{c5::existiert mit $r_f(e) = c$}}</td><td>{{c6::existiert nicht}}</td></tr></table>
Extra		Saturierte Kanten produzieren nur die Rückwärtskante, leere Kanten nur die Vorwärtskante. Dazwischen entsteht ein „Doppelpfeil“ mit beiden Restkapazitäten.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 14: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Vixq;:@kAb

added

Note did not exist

New Note

Front

Da es nur endlich viele s-t-Schnitte gibt, folgt:

s-t-MinCut ist ein endliches algorithmisches Problem,
ein minimaler Schnitt existiert immer.

Back

Da es nur endlich viele s-t-Schnitte gibt, folgt:

s-t-MinCut ist ein endliches algorithmisches Problem,
ein minimaler Schnitt existiert immer.

Im Gegensatz dazu ist die Menge der zulässigen Flüsse im Allgemeinen unendlich (reelle Kapazitäten), aber das Supremum wird ebenfalls angenommen (Maxflow-Mincut).

Field-by-field Comparison

Field	Before	After
Text		Da es nur {{c1::endlich viele s-t-Schnitte}} gibt, folgt:<ul><li>s-t-MinCut ist {{c2::ein endliches algorithmisches Problem}},</li><li>{{c3::ein minimaler Schnitt existiert immer}}.</li></ul>
Extra		Im Gegensatz dazu ist die Menge der zulässigen Flüsse im Allgemeinen unendlich (reelle Kapazitäten), aber das Supremum wird ebenfalls angenommen (Maxflow-Mincut).

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 15: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Y!-po8YFmj

added

Note did not exist

New Note

Front

Lemma (Nettozufluss der Senke). Für jeden Fluss $f$ gilt: der Nettozufluss der Senke gleicht dem Wert des Flusses:\[\operatorname{netinflow}(t) := \sum_{u \in V : (u,t) \in A} f(u, t) \;-\; \sum_{u \in V : (t,u) \in A} f(t, u) \;=\; {{c2::\operatorname{val}(f)}}.\]

Back

Intuition: Was bei der Quelle herausfliesst, muss bei der Senke ankommen. Beweis via Flusserhaltung an den inneren Knoten und Aufsummieren über alle $v \in V \setminus \{s\}$. Proof Included

Field-by-field Comparison

Field	Before	After
Text		<b>Lemma (Nettozufluss der Senke).</b> Für jeden Fluss $f$ gilt: der Nettozufluss der Senke gleicht {{c1::dem Wert des Flusses}}:\[\operatorname{netinflow}(t) := \sum_{u \in V : (u,t) \in A} f(u, t) \;-\; \sum_{u \in V : (t,u) \in A} f(t, u) \;=\; {{c2::\operatorname{val}(f)}}.\]
Extra		Intuition: Was bei der Quelle herausfliesst, muss bei der Senke ankommen. Beweis via Flusserhaltung an den inneren Knoten und Aufsummieren über alle $v \in V \setminus \{s\}$. <i>Proof Included</i>

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 16: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: [I%rT#:,Sz

added

Note did not exist

New Note

Front

Notation. Für eine Kante $e = (u, v)$ sei $e^{\mathrm{opp}} := (v, u)$. Im Spielraum einer Kante mit Kapazität $c$ und Fluss $f$ haben wir vorwärts den Vorrat $c - f$ und rückwärts den Vorrat $f$.

Back

Vorwärts: noch $c - f$ zusätzliche Einheiten möglich. Rückwärts: bis zu $f$ Einheiten lassen sich „zurückgeben“. Diese beiden Werte werden im Restnetzwerk zu zwei separaten Kanten.

Field-by-field Comparison

Field	Before	After
Text		<b>Notation.</b> Für eine Kante $e = (u, v)$ sei $e^{\mathrm{opp}} := {{c1::(v, u)}}$. Im <b>Spielraum</b> einer Kante mit Kapazität $c$ und Fluss $f$ haben wir vorwärts den Vorrat ${{c2::c - f}}$ und rückwärts den Vorrat ${{c3::f}}$.
Extra		Vorwärts: noch $c - f$ zusätzliche Einheiten möglich. Rückwärts: bis zu $f$ Einheiten lassen sich „zurückgeben“. Diese beiden Werte werden im Restnetzwerk zu zwei separaten Kanten.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 17: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: ^b{k*,vo>I

added

Note did not exist

New Note

Front

Schreibe den Ford-Fulkerson-Algorithmus als Pseudocode.

Back

Schreibe den Ford-Fulkerson-Algorithmus als Pseudocode.

Ford-Fulkerson(V, A, c, s, t)
1: f := 0                    // Fluss konstant 0
2: while exists s-t-Pfad P in N_f do  // augmentierender Pfad
3:     Augmentiere den Fluss entlang P
4: return f                  // maximaler Fluss

Korrektheit folgt direkt aus dem Charakterisierungssatz: bei Terminierung gibt es keinen s-t-Pfad in $N_f$, also ist $f$ maximal.

Field-by-field Comparison

Field	Before	After
Front		Schreibe den <b>Ford-Fulkerson</b>-Algorithmus als Pseudocode.
Back		<pre>Ford-Fulkerson(V, A, c, s, t) 1: f := 0 // Fluss konstant 0 2: while exists s-t-Pfad P in N_f do // augmentierender Pfad 3: Augmentiere den Fluss entlang P 4: return f // maximaler Fluss</pre>Korrektheit folgt direkt aus dem Charakterisierungssatz: bei Terminierung gibt es keinen s-t-Pfad in $N_f$, also ist $f$ maximal.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 18: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: a(.3t3[#-=

added

Note did not exist

New Note

Front

Sei $N = (V, A, c, s, t)$ ein Netzwerk. Ein Fluss in $N$ ist eine Funktion $f : A \to \mathbb{R}$ mit:

Zulässigkeit: \[{{c2::0 \leq f(e) \leq c(e) \quad \text{für alle } e \in A}}\]
Flusserhaltung: für alle $v \in V \setminus \{s, t\}$ gilt \[{{c4::\sum_{u \in V : (u,v) \in A} f(u, v) \;=\; \sum_{u \in V : (v,u) \in A} f(v, u)}}\]

Back

Sei $N = (V, A, c, s, t)$ ein Netzwerk. Ein Fluss in $N$ ist eine Funktion $f : A \to \mathbb{R}$ mit:

Zulässigkeit: \[{{c2::0 \leq f(e) \leq c(e) \quad \text{für alle } e \in A}}\]
Flusserhaltung: für alle $v \in V \setminus \{s, t\}$ gilt \[{{c4::\sum_{u \in V : (u,v) \in A} f(u, v) \;=\; \sum_{u \in V : (v,u) \in A} f(v, u)}}\]

Flusserhaltung gilt nur an inneren Knoten, nicht an Quelle oder Senke. Anschaulich: was hineinfliesst, fliesst auch hinaus.

Field-by-field Comparison

Field	Before	After
Text		Sei $N = (V, A, c, s, t)$ ein Netzwerk. Ein <b>Fluss</b> in $N$ ist eine Funktion $f : A \to \mathbb{R}$ mit:<ul><li>{{c1::<b>Zulässigkeit</b>}}: \[{{c2::0 \leq f(e) \leq c(e) \quad \text{für alle } e \in A}}\]</li><li>{{c3::<b>Flusserhaltung</b>}}: für alle $v \in V \setminus \{s, t\}$ gilt \[{{c4::\sum_{u \in V : (u,v) \in A} f(u, v) \;=\; \sum_{u \in V : (v,u) \in A} f(v, u)}}\]</li></ul>
Extra		Flusserhaltung gilt nur an inneren Knoten, nicht an Quelle oder Senke. Anschaulich: was hineinfliesst, fliesst auch hinaus.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 19: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID: iZ)F7%YzkN

added

Note did not exist

New Note

Front

Nenne klassische Anwendungen des MaxFlow-Problems.

Back

Nenne klassische Anwendungen des MaxFlow-Problems.

Verkehrsflüsse, Geldflüsse, Transportprobleme
Bildsegmentierung in der Bildverarbeitung
Matchings in Graphen
Schnitte (Cuts) in Graphen
Disjunkte Wege in Graphen

Historisch motiviert durch das russische Schienennetz (A. N. Tolstoĭ 1930, Harris & Ross 1955).

Field-by-field Comparison

Field	Before	After
Front		Nenne klassische Anwendungen des <b>MaxFlow</b>-Problems.
Back		<ul><li>Verkehrsflüsse, Geldflüsse, Transportprobleme</li><li>Bildsegmentierung in der Bildverarbeitung</li><li>Matchings in Graphen</li><li>Schnitte (Cuts) in Graphen</li><li>Disjunkte Wege in Graphen</li></ul>Historisch motiviert durch das russische Schienennetz (A. N. Tolstoĭ 1930, Harris & Ross 1955).

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 20: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: lg(2GdY~w`

added

Note did not exist

New Note

Front

Lemma (schwache Dualität). Ist $f$ ein Fluss und $(S, T)$ ein s-t-Schnitt in einem Netzwerk, so gilt\[{{c1::\operatorname{val}(f) \;\leq\; \operatorname{cap}(S, T)}}.\]

Back

Lemma (schwache Dualität). Ist $f$ ein Fluss und $(S, T)$ ein s-t-Schnitt in einem Netzwerk, so gilt\[{{c1::\operatorname{val}(f) \;\leq\; \operatorname{cap}(S, T)}}.\]

Konsequenz: Findet man zu einem Fluss $f$ einen Schnitt $(S, T)$ mit $\operatorname{val}(f) = \operatorname{cap}(S, T)$, so ist $f$ maximal. Der Schnitt ist dann ein einfaches Zertifikat für die Maximalität.

Field-by-field Comparison

Field	Before	After
Text		<b>Lemma (schwache Dualität).</b> Ist $f$ ein Fluss und $(S, T)$ ein s-t-Schnitt in einem Netzwerk, so gilt\[{{c1::\operatorname{val}(f) \;\leq\; \operatorname{cap}(S, T)}}.\]
Extra		Konsequenz: Findet man zu einem Fluss $f$ einen Schnitt $(S, T)$ mit $\operatorname{val}(f) = \operatorname{cap}(S, T)$, so ist $f$ maximal. Der Schnitt ist dann ein einfaches Zertifikat für die Maximalität.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::2._Flüsse_in_Netzwerken

Note 21: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: mZ>kn$y)WC

added

Note did not exist

New Note

Front

Maxflow-Mincut-Theorem (ganzzahlig, konstruktiv). Jedes Netzwerk mit ganzzahligen Kapazitäten erfüllt\[\max_{f \text{ Fluss}} \operatorname{val}(f) \;=\; \min_{(S, T) \text{ s-t-Schnitt}} \operatorname{cap}(S, T).\]Der Beweis ist konstruktiv: nach Terminierung von Ford-Fulkerson liefert {{c1::$S := \{v \in V : v \text{ in } N_f \text{ von } s \text{ erreichbar}\}$}} einen Schnitt mit {{c2::$\operatorname{cap}(S, T) = \operatorname{val}(f)$}}.

Back

Die ganzzahlige Variante folgt direkt aus dem Charakterisierungssatz und der Termination von Ford-Fulkerson bei $c : A \to \mathbb{N}_0$. Im reellwertigen Fall verlangt der Beweis ein Kompaktheits-/Grenzwertargument.

Field-by-field Comparison

Field	Before	After
Text		<b>Maxflow-Mincut-Theorem (ganzzahlig, konstruktiv).</b> Jedes Netzwerk mit ganzzahligen Kapazitäten erfüllt\[\max_{f \text{ Fluss}} \operatorname{val}(f) \;=\; \min_{(S, T) \text{ s-t-Schnitt}} \operatorname{cap}(S, T).\]Der Beweis ist konstruktiv: nach Terminierung von Ford-Fulkerson liefert {{c1::$S := \{v \in V : v \text{ in } N_f \text{ von } s \text{ erreichbar}\}$}} einen Schnitt mit {{c2::$\operatorname{cap}(S, T) = \operatorname{val}(f)$}}.
Extra		Die ganzzahlige Variante folgt direkt aus dem Charakterisierungssatz und der Termination von Ford-Fulkerson bei $c : A \to \mathbb{N}_0$. Im reellwertigen Fall verlangt der Beweis ein Kompaktheits-/Grenzwertargument.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 22: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: sny.5hw<$2

added

Note did not exist

New Note

Front

Eigenschaften des Ford-Fulkerson-Algorithmus bezüglich Termination:

Allgemein: Terminierung ist nicht garantiert.
Bei Kapazitäten in $\mathbb{R}$: der Algorithmus kann unendlich laufen.
Bei Kapazitäten in $\mathbb{N}_0$: Flüsse und Restkapazitäten bleiben ganzzahlig, und der Fluss verbessert sich pro Augmentierung um mindestens $1$.

Back

Eigenschaften des Ford-Fulkerson-Algorithmus bezüglich Termination:

Allgemein: Terminierung ist nicht garantiert.
Bei Kapazitäten in $\mathbb{R}$: der Algorithmus kann unendlich laufen.
Bei Kapazitäten in $\mathbb{N}_0$: Flüsse und Restkapazitäten bleiben ganzzahlig, und der Fluss verbessert sich pro Augmentierung um mindestens $1$.

Bei reellen (sogar irrationalen) Kapazitäten gibt es Beispiele, in denen Ford-Fulkerson zwar konvergiert, aber gegen einen falschen Wert oder gar nicht. Die Wahl des augmentierenden Pfads (z.B. via BFS bei Edmonds-Karp) liefert eine Polynomialzeitschranke unabhängig von $U$.

Field-by-field Comparison

Field	Before	After
Text		Eigenschaften des Ford-Fulkerson-Algorithmus bezüglich Termination:<ul><li>Allgemein: {{c1::Terminierung ist nicht garantiert}}.</li><li>Bei Kapazitäten in $\mathbb{R}$: {{c2::der Algorithmus kann unendlich laufen}}.</li><li>Bei Kapazitäten in $\mathbb{N}_0$: {{c3::Flüsse und Restkapazitäten bleiben ganzzahlig}}, und der Fluss verbessert sich pro Augmentierung um {{c4::mindestens $1$}}.</li></ul>
Extra		Bei reellen (sogar irrationalen) Kapazitäten gibt es Beispiele, in denen Ford-Fulkerson zwar konvergiert, aber gegen einen falschen Wert oder gar nicht. Die Wahl des augmentierenden Pfads (z.B. via BFS bei Edmonds-Karp) liefert eine Polynomialzeitschranke unabhängig von $U$.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 23: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: so%HV=os_e

added

Note did not exist

New Note

Front

Beweis von „Pfad in $N_f$ $\Rightarrow$ $f$ nicht maximal“. Gegeben ein gerichteter s-t-Pfad in $N_f$ mit Restkapazitäten $\varepsilon_1, \ldots, \varepsilon_k$. Setze $\varepsilon := \min_i \varepsilon_i > 0$. Augmentiere $f$ entlang des Pfads um $\varepsilon$: auf Vorwärtskanten $+\varepsilon$, auf Rückwärtskanten $-\varepsilon$. Der neue Fluss ist zulässig (durch Wahl von $\varepsilon$) und flusserhaltend, und es gilt $\operatorname{val}(f') = {{c5::\operatorname{val}(f) + \varepsilon}}$.

Back

Zulässigkeit: bei $+\varepsilon$ bleibt man unter $c$, weil $\varepsilon \leq c - f$; bei $-\varepsilon$ bleibt man über $0$, weil $\varepsilon \leq f$.

Field-by-field Comparison

Field	Before	After
Text		<b>Beweis von „Pfad in $N_f$ $\Rightarrow$ $f$ nicht maximal“.</b> Gegeben ein gerichteter s-t-Pfad in $N_f$ mit Restkapazitäten $\varepsilon_1, \ldots, \varepsilon_k$. Setze $\varepsilon := {{c1::\min_i \varepsilon_i}} > 0$. Augmentiere $f$ entlang des Pfads um $\varepsilon$: auf Vorwärtskanten {{c2::$+\varepsilon$}}, auf Rückwärtskanten {{c3::$-\varepsilon$}}. Der neue Fluss ist {{c4::zulässig (durch Wahl von $\varepsilon$) und flusserhaltend}}, und es gilt $\operatorname{val}(f') = {{c5::\operatorname{val}(f) + \varepsilon}}$.
Extra		Zulässigkeit: bei $+\varepsilon$ bleibt man unter $c$, weil $\varepsilon \leq c - f$; bei $-\varepsilon$ bleibt man über $0$, weil $\varepsilon \leq f$.

Tags: ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Note 24: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:

u!h9


            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen
  
  
    Satz (Charakterisierung maximaler Fluss). Sei \(N\) ein Netzwerk ohne entgegen gerichtete Kanten. Dann gilt:\(f\) ist maximaler Fluss \(\iff\) im Restnetzwerk \(N_f\) gibt es keinen gerichteten s-t-Pfad.
Für jeden maximalen Fluss \(f\) gibt es einen s-t-Schnitt \((S, T)\) mit {{c2::\(\operatorname{val}(f) = \operatorname{cap}(S, T)\)}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen
  
  
    Satz (Charakterisierung maximaler Fluss). Sei \(N\) ein Netzwerk ohne entgegen gerichtete Kanten. Dann gilt:\(f\) ist maximaler Fluss \(\iff\) im Restnetzwerk \(N_f\) gibt es keinen gerichteten s-t-Pfad.
Für jeden maximalen Fluss \(f\) gibt es einen s-t-Schnitt \((S, T)\) mit {{c2::\(\operatorname{val}(f) = \operatorname{cap}(S, T)\)}}.
    
    
    
    Der zweite Punkt liefert konstruktiv das Maxflow-Mincut-Theorem. Proof Included
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            <b>Satz (Charakterisierung maximaler Fluss).</b> Sei \(N\) ein Netzwerk ohne entgegen gerichtete Kanten. Dann gilt:<ul><li>\(f\) ist maximaler Fluss \(\iff\) {{c1::im Restnetzwerk \(N_f\) gibt es keinen gerichteten s-t-Pfad}}.</li><li>Für jeden maximalen Fluss \(f\) gibt es einen s-t-Schnitt \((S, T)\) mit {{c2::\(\operatorname{val}(f) = \operatorname{cap}(S, T)\)}}.</li></ul>
                        
                        
                        
                            Extra
                            
                            Der zweite Punkt liefert konstruktiv das Maxflow-Mincut-Theorem. <i>Proof Included</i>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen

Field	Before	After
Text		<b>Satz (Charakterisierung maximaler Fluss).</b> Sei \(N\) ein Netzwerk ohne entgegen gerichtete Kanten. Dann gilt:<ul><li>\(f\) ist maximaler Fluss \(\iff\) {{c1::im Restnetzwerk \(N_f\) gibt es keinen gerichteten s-t-Pfad}}.</li><li>Für jeden maximalen Fluss \(f\) gibt es einen s-t-Schnitt \((S, T)\) mit {{c2::\(\operatorname{val}(f) = \operatorname{cap}(S, T)\)}}.</li></ul>
Extra		Der zweite Punkt liefert konstruktiv das Maxflow-Mincut-Theorem. <i>Proof Included</i>


        
        
            Note 25: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: vi;%r.~JIf
            
            added
            

            
            
            
                
                    Previous
                    Note did not exist
                
                
                    New Note
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen
  
  
    Eine Flussaugmentierung ist eine Folge von lokalen Veränderungen entlang eines s-t-Pfads, bei dem auf jeder Kante entweder \(+\delta\) (in Vorwärtsrichtung) oder \(-\delta\) (in Rückwärtsrichtung) addiert wird. Da an Quelle und Senke keine Flusserhaltung gefordert ist, erhöht sich \(\operatorname{val}(f)\) genau um \(\delta\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen
  
  
    Eine Flussaugmentierung ist eine Folge von lokalen Veränderungen entlang eines s-t-Pfads, bei dem auf jeder Kante entweder \(+\delta\) (in Vorwärtsrichtung) oder \(-\delta\) (in Rückwärtsrichtung) addiert wird. Da an Quelle und Senke keine Flusserhaltung gefordert ist, erhöht sich \(\operatorname{val}(f)\) genau um \(\delta\).
    
    
    
    Beachte: Augmentierende Pfade aus dem Matching-Kapitel sind ein verwandtes, aber anderes Konzept (alternierende Kanten in/aus \(M\)). Hier geht es um Restkapazitäten in einem Netzwerk.
  



                        
                    
                    
                
            

            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            
                            Eine <b>Flussaugmentierung</b> ist eine Folge von lokalen Veränderungen entlang eines s-t-Pfads, bei dem auf jeder Kante entweder \(+\delta\) (in Vorwärtsrichtung) oder \(-\delta\) (in Rückwärtsrichtung) addiert wird. Da {{c1::an Quelle und Senke keine Flusserhaltung gefordert ist}}, erhöht sich \(\operatorname{val}(f)\) genau um {{c2::\(\delta\)}}.
                        
                        
                        
                            Extra
                            
                            <b>Beachte:</b> Augmentierende Pfade aus dem Matching-Kapitel sind ein verwandtes, aber anderes Konzept (alternierende Kanten in/aus \(M\)). Hier geht es um Restkapazitäten in einem Netzwerk.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::3._Algorithmen_-_Highlights::1._Graphenalgorithmen::3._Minimale_Schnitte_in_Graphen
                    
                
            
            
        
        
        
            Note 26: ETH::2. Semester::A&W
            
                Deck: ETH::2. Semester::A&W

                Note Type: Horvath Cloze

                GUID: z0k}SHzjrH
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
    
    
    
    Das ist ein typisches Adversary-Argument: Der "Gegenspieler" entscheidet die Eingabe erst während der Ausführung, immer so, dass der Algorithmus möglichst lange braucht. Da der Algorithmus deterministisch ist, weiss der Adversary genau, welche Position als nächstes gelesen wird, und kann sie auf \(0\) setzen.
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::6._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::6._Üppige-Auswahl-Problem
  
  
    Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega(n)\).

Beweisidee (Adversary-Argument): 
Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens \(n/2 + 1\) Eingabezahlen, bevor er eine \(1\) sieht.
    
    
    
    Das ist ein typisches Adversary-Argument: Der "Gegenspieler" entscheidet die Eingabe erst während der Ausführung, immer so, dass der Algorithmus möglichst lange braucht. Da der Algorithmus deterministisch ist, weiss der Adversary genau, welche Position als nächstes gelesen wird, und kann sie auf \(0\) setzen.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega({{c1::n}})\).<br><br><b>Beweisidee (Adversary-Argument):</b> <br>Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit&nbsp;{{c2::\(0\)}}, solange wir noch nicht \(n/2\) Nullen platziert haben. Sobald \(n/2\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens {{c3::\(n/2 + 1\)}} Eingabezahlen, bevor er eine \(1\) sieht.
                            Jeder deterministische Algorithmus für das Üppige-Auswahl-Problem benötigt Laufzeit \(\Omega({{c1::n}})\).<br><br><b>Beweisidee (Adversary-Argument):</b> <br>Für fixen Algorithmus konstruieren wir die Instanz schrittweise. Auf jede Anfrage \(x_i\) des Algorithmus antworten wir mit \(0\), solange wir noch nicht \({{c2::n/2}}\) Nullen platziert haben. Sobald \({{c2::n/2}}\) Nullen platziert sind, füllen wir die restlichen Positionen mit \(1\) auf. Damit liest der Algorithmus mindestens {{c3::\(n/2 + 1\)}} Eingabezahlen, bevor er eine \(1\) sieht.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::5._Üppige-Auswahl-Problem
                    
                    
                    
                    
                    
                    ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::8._Randomisierte_Algorithmen::6._Üppige-Auswahl-Problem
                    
                
            
            
        
        
        
            Note 27: ETH::2. Semester::PProg
            
                Deck: ETH::2. Semester::PProg

                Note Type: Horvath Cloze

                GUID: 7c[p[vx$A1
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    An atomic register \(r\) (a shared memory object, not a CPU register) supports r.read() and r.write(v) with four properties: each invocation \(J\) takes effect at a single point in time \(\tau(J)\); \(\tau(J)\) lies between the start and end of \(J\); two operations on the same register have distinct effect times \(\tau(J) \neq \tau(K)\); an invocation of r.read() returns the value written by the r.write(v) invocation with the closest preceding effect time.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    An atomic register \(r\) (a shared memory object, not a CPU register) supports r.read() and r.write(v) with four properties: each invocation \(J\) takes effect at a single point in time \(\tau(J)\); \(\tau(J)\) lies between the start and end of \(J\); two operations on the same register have distinct effect times \(\tau(J) \neq \tau(K)\); an invocation of r.read() returns the value written by the r.write(v) invocation with the closest preceding effect time.
    
    
    
    These four conditions justify treating each operation as if it happened instantaneously at \(\tau(J)\), even though physically it spans an interval. This is the foundation for proofs about Peterson, Filter, Bakery, etc.
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    An atomic register \(r\) (a shared memory object, not a CPU register) supports r.read() and r.write(v) with four properties: 
Each invocation \(J\) takes effect at a single point in time \(\tau(J)\).
\(\tau(J)\) lies between the start and end of \(J\). 
Two operations on the same register have distinct effect times \(\tau(J) \neq \tau(K)\).
An invocation of r.read() returns the value written by the r.write(v) invocation with the closest preceding effect time.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    An atomic register \(r\) (a shared memory object, not a CPU register) supports r.read() and r.write(v) with four properties: 
Each invocation \(J\) takes effect at a single point in time \(\tau(J)\).
\(\tau(J)\) lies between the start and end of \(J\). 
Two operations on the same register have distinct effect times \(\tau(J) \neq \tau(K)\).
An invocation of r.read() returns the value written by the r.write(v) invocation with the closest preceding effect time.
    
    
    
    These four conditions justify treating each operation as if it happened instantaneously at \(\tau(J)\), even though physically it spans an interval. This is the foundation for proofs about Peterson, Filter, Bakery, etc.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            An <i>atomic register</i> \(r\) (a shared memory object, not a CPU register) supports <code>r.read()</code> and <code>r.write(v)</code> with four properties: each invocation \(J\) {{c1::takes effect at a single point in time \(\tau(J)\)}}; \(\tau(J)\) {{c1::lies between the start and end of \(J\)}}; two operations on the same register {{c1::have distinct effect times \(\tau(J) \neq \tau(K)\)}}; an invocation of <code>r.read()</code> returns {{c1::the value written by the <code>r.write(v)</code> invocation with the closest preceding effect time}}.
                            An <i>atomic register</i> \(r\) (a shared memory object, not a CPU register) supports <code>r.read()</code> and <code>r.write(v)</code> with four properties: <br><ol><li>Each invocation \(J\)&nbsp;takes effect {{c1::at a single point in time \(\tau(J)\)}}.</li><li>\(\tau(J)\)&nbsp;lies between {{c2::the start and end of \(J\)}}.&nbsp;</li><li>Two operations on the same register have {{c3::distinct effect times \(\tau(J) \neq \tau(K)\)}}.</li><li>An invocation of <code>r.read()</code> returns {{c4::the value written by the <code>r.write(v)</code> invocation with the closest preceding effect time}}.</li></ol>
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
                    
                    
                    
                
            
            
        
        
        
            Note 28: ETH::2. Semester::PProg
            
                Deck: ETH::2. Semester::PProg

                Note Type: Horvath Cloze

                GUID: Jj5bulRE#&
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    

Here the order "first wait for the neighbour, then set my own flag" violates mutual exclusion, because {{c2::both threads can leave their while with wantp{=}wantq{=}false before either of them sets its flag}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    

Here the order "first wait for the neighbour, then set my own flag" violates mutual exclusion, because {{c2::both threads can leave their while with wantp{=}wantq{=}false before either of them sets its flag}}.
    
    
    
    Both threads enter the CS together; visible as state \((p4, q4, true, true)\) in the state-space diagram.

Naive fix: set the flag before the check. That solves ME but creates new problems (deadlock/livelock); see Dekker / Peterson.
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    

Here the order "first wait for the neighbour, then set my own flag" violates mutual exclusion, because {{c1::both threads can leave their while with wantp{=}wantq{=}false before either of them sets its flag}}.
  



                        
                    
                    
                        Back
                        
                            
  ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers
  
  
    

Here the order "first wait for the neighbour, then set my own flag" violates mutual exclusion, because {{c1::both threads can leave their while with wantp{=}wantq{=}false before either of them sets its flag}}.
    
    
    
    Both threads enter the CS together; visible as state \((p4, q4, true, true)\) in the state-space diagram.

Naive fix: set the flag before the check. That solves ME but creates new problems (deadlock/livelock); see Dekker / Peterson.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Text
                            <img src="paste-2c297c3fe3ab4f7a63914ae8ad4be81fa93d9e11.jpg"><br><br>Here the order "first wait for the neighbour, then set my own flag" violates {{c1::mutual exclusion}}, because {{c2::both threads can leave their <code>while</code> with <code>wantp{=}wantq{=}false</code> before either of them sets its flag}}.
                            <img src="paste-2c297c3fe3ab4f7a63914ae8ad4be81fa93d9e11.jpg"><br><br>Here the order "first wait for the neighbour, then set my own flag" violates {{c1::mutual exclusion}}, because {{c1::both threads can leave their <code>while</code> with <code>wantp{=}wantq{=}false</code> before either of them sets its flag}}.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::2._Semester::PProg::12._Shared_Memory_Concurrency::5._Locks_with_Atomic_Registers

Fluss \(f\)	Vorwärtskante \(e\)	Rückwärtskante \(e^{\mathrm{opp}}\)
\(0 < f < c\)	existiert mit \(r_f(e) = c - f\)	existiert mit \(r_f(e^{\mathrm{opp) = f\)}}
\(f = c\) (saturiert)	existiert nicht	existiert mit \(r_f(e^{\mathrm{opp) = c\)}}
\(f = 0\)	existiert mit \(r_f(e) = c\)	existiert nicht

Fluss \(f\)	Vorwärtskante \(e\)	Rückwärtskante \(e^{\mathrm{opp}}\)
\(0 < f < c\)	existiert mit \(r_f(e) = c - f\)	existiert mit \(r_f(e^{\mathrm{opp) = f\)}}
\(f = c\) (saturiert)	existiert nicht	existiert mit \(r_f(e^{\mathrm{opp) = c\)}}
\(f = 0\)	existiert mit \(r_f(e) = c\)	existiert nicht

Field	Before	After
Text		Sei \(N = (V, A, c, s, t)\) ein Netzwerk ohne entgegen gerichtete Kanten und \(f\) ein Fluss in \(N\). Das <b>Restnetzwerk</b> \(N_f := (V, A_f, r_f, s, t)\) ist definiert durch:<ol><li>Ist \(e \in A\) mit \({{c1::f(e) < c(e)}}\), dann ist \(e\) eine Kante in \(A_f\) mit \(r_f(e) := {{c2::c(e) - f(e)}}\).</li><li>Ist \(e \in A\) mit \({{c3::f(e) > 0}}\), dann ist \(e^{\mathrm{opp}}\) in \(A_f\) mit \(r_f(e^{\mathrm{opp}}) := {{c4::f(e)}}\).</li><li>\(A_f\) enthält {{c5::nur Kanten wie in (1) und (2)}}.</li></ol>Den Wert \(r_f(e)\) nennen wir die <b>Restkapazität</b> der Kante \(e\).
Extra		Die Annahme „ohne entgegen gerichtete Kanten“ ist nur eine Vereinfachung, nicht essentiell. Sie sorgt dafür, dass \(e\) und \(e^{\mathrm{opp}}\) eindeutig auseinanderzuhalten sind.

Field	Before	After
Text		<b>Beweis von „kein Pfad in \(N_f\) \(\Rightarrow\) \(\exists\) Schnitt \((S, T)\) mit \(\operatorname{cap}(S, T) = \operatorname{val}(f)\)“.</b> Definiere\[\begin{gathered}S := {{c1::\{v \in V : v \text{ ist von } s \text{ in } N_f \text{ erreichbar}\}}}, \\T := V \setminus S.\end{gathered}\]Da kein s-t-Pfad in \(N_f\) existiert, gilt {{c2::\(t \in T\)}}, also ist \((S, T)\) ein s-t-Schnitt. Für jede Kante \((u, w) \in S \times T\) im Originalnetzwerk gilt {{c3::\(f(u, w) = c(u, w)\)}} (sonst wäre \(w\) erreichbar), und für \((w, u) \in T \times S\) gilt {{c4::\(f(w, u) = 0\)}} (sonst gäbe es \((u, w)^{\mathrm{opp}}\) im Restnetzwerk). Damit \(\operatorname{val}(f) = f(S, T) - f(T, S) = \operatorname{cap}(S, T) - 0\).
Extra		Die zwei Bedingungen geben gleichzeitig die untere und die obere Schranke aus dem schwachen Dualitätslemma scharf: alle vorwärtsführenden Kanten sind saturiert, alle rückwärtsführenden Kanten tragen keinen Fluss.

Field	Before	After
Text		Für eine Partition \((U, W)\) von \(V\) sei \(f(U, W) := \sum_{(u, w) \in (U \times W) \cap A} f(u, w)\). Im Beweis von \(\operatorname{val}(f) \leq \operatorname{cap}(S, T)\) zeigt man:\[\begin{gathered}\operatorname{val}(f) \;\overset{(\text{i})}{=}\; {{c1::f(S, T) - f(T, S)}} \\\overset{(\text{ii})}{\leq}\; {{c2::f(S, T)}} \\\overset{(\text{iii})}{\leq}\; \operatorname{cap}(S, T)\end{gathered}\]
Extra		<ul><li>(i) Aufsummieren der Flusserhaltung über alle \(v \in S\) (mit \(s \in S\)) und Ausnutzung der Definition \(\operatorname{val}(f) = \operatorname{netoutflow}(s)\).</li><li>(ii) \(f(T, S) \geq 0\), da \(f \geq 0\) auf jeder Kante.</li><li>(iii) \(f(u, w) \leq c(u, w)\) für jede Kante (Zulässigkeit).</li></ul>

Field	Before	After
Text		Der <b>Wert</b> eines Flusses \(f\) ist definiert als der {{c1::Nettoabfluss der Quelle}}:\[\operatorname{val}(f) := \operatorname{netoutflow}(s) := {{c2::\sum_{u \in V : (s,u) \in A} f(s, u) \;-\; \sum_{u \in V : (u,s) \in A} f(u, s)}}.\]
Extra		Eingehende Kanten an der Quelle werden abgezogen.

Field	Before	After
Text		Ein <b>Netzwerk</b> ist ein Tupel \(N = (V, A, c, s, t)\), wobei:<ul><li>\((V, A)\) ist {{c1::ein gerichteter Graph (ohne Schleifen)}},</li><li>\(s \in V\) ist {{c2::die <i>Quelle</i>}},</li><li>\(t \in V \setminus \{s\}\) ist {{c3::die <i>Senke</i>}},</li><li>\(c : A \to \mathbb{R}_0^+\) ist {{c4::die <i>Kapazitätsfunktion</i>}}.</li></ul>
Extra		Quelle und Senke müssen verschieden sein. Kapazitäten sind nichtnegativ reell.

Field	Before	After
Text		<b>Notation.</b> Für eine Kante \(e = (u, v)\) sei \(e^{\mathrm{opp}} := {{c1::(v, u)}}\). Im <b>Spielraum</b> einer Kante mit Kapazität \(c\) und Fluss \(f\) haben wir vorwärts den Vorrat \({{c2::c - f}}\) und rückwärts den Vorrat \({{c3::f}}\).
Extra		Vorwärts: noch \(c - f\) zusätzliche Einheiten möglich. Rückwärts: bis zu \(f\) Einheiten lassen sich „zurückgeben“. Diese beiden Werte werden im Restnetzwerk zu zwei separaten Kanten.

Field	Before	After
Text		<b>Lemma (schwache Dualität).</b> Ist \(f\) ein Fluss und \((S, T)\) ein s-t-Schnitt in einem Netzwerk, so gilt\[{{c1::\operatorname{val}(f) \;\leq\; \operatorname{cap}(S, T)}}.\]
Extra		Konsequenz: Findet man zu einem Fluss \(f\) einen Schnitt \((S, T)\) mit \(\operatorname{val}(f) = \operatorname{cap}(S, T)\), so ist \(f\) maximal. Der Schnitt ist dann ein einfaches Zertifikat für die Maximalität.

Field	Before	After
Text		<b>Beweis von „Pfad in \(N_f\) \(\Rightarrow\) \(f\) nicht maximal“.</b> Gegeben ein gerichteter s-t-Pfad in \(N_f\) mit Restkapazitäten \(\varepsilon_1, \ldots, \varepsilon_k\). Setze \(\varepsilon := {{c1::\min_i \varepsilon_i}} > 0\). Augmentiere \(f\) entlang des Pfads um \(\varepsilon\): auf Vorwärtskanten {{c2::\(+\varepsilon\)}}, auf Rückwärtskanten {{c3::\(-\varepsilon\)}}. Der neue Fluss ist {{c4::zulässig (durch Wahl von \(\varepsilon\)) und flusserhaltend}}, und es gilt \(\operatorname{val}(f') = {{c5::\operatorname{val}(f) + \varepsilon}}\).
Extra		Zulässigkeit: bei \(+\varepsilon\) bleibt man unter \(c\), weil \(\varepsilon \leq c - f\); bei \(-\varepsilon\) bleibt man über \(0\), weil \(\varepsilon \leq f\).

Field	Before	After
Text		Eine <b>Flussaugmentierung</b> ist eine Folge von lokalen Veränderungen entlang eines s-t-Pfads, bei dem auf jeder Kante entweder \(+\delta\) (in Vorwärtsrichtung) oder \(-\delta\) (in Rückwärtsrichtung) addiert wird. Da {{c1::an Quelle und Senke keine Flusserhaltung gefordert ist}}, erhöht sich \(\operatorname{val}(f)\) genau um {{c2::\(\delta\)}}.
Extra		<b>Beachte:</b> Augmentierende Pfade aus dem Matching-Kapitel sind ein verwandtes, aber anderes Konzept (alternierende Kanten in/aus \(M\)). Hier geht es um Restkapazitäten in einem Netzwerk.