From 099c6750027b87cf4a17a0bb88581f2bd927eaa0 Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <paul.jungeblut@gmail.com>
Date: Fri, 8 Jan 2016 23:30:32 +0100
Subject: Adding a push relabel max flow algorithm to the TCR.

---
 graph/graph.tex | 37 ++++++++++++++++++++++++-------------
 1 file changed, 24 insertions(+), 13 deletions(-)

(limited to 'graph/graph.tex')

diff --git a/graph/graph.tex b/graph/graph.tex
index 0661ae1..4a617a8 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -77,21 +77,32 @@ Erkennt negative Zyklen.
 \subsection{Max-Flow}
 
 \subsubsection{Capacity Scaling}
+Gut bei dünn besetzten Graphen.
 \lstinputlisting{graph/capacityScaling.cpp}
 
-\subsubsection{Maximum Edge Disjoint Paths}
-Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
-\begin{enumerate}
-	\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1.
-	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Kanten.
-\end{enumerate}
-
-\subsubsection{Maximum Independent Paths}
-Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
-\begin{enumerate}
-	\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1.
-	\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten.
-\end{enumerate}
+\subsubsection{Push Relabel}
+Gut bei sehr dicht besetzten Graphen.
+\lstinputlisting{graph/pushRelabel.cpp}
+
+\subsubsection{Anwendungen}
+\begin{itemize}
+	\item \textbf{Maximum Edge Disjoint Paths}\newline
+	Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
+	\begin{enumerate}
+		\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante auf 1.
+		\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Kanten.
+	\end{enumerate}
+	\item \textbf{Maximum Independent Paths}\newline
+	Finde die maximale Anzahl Pfade von $s$ nach $t$, die keinen Knoten teilen.
+	\begin{enumerate}
+		\item Setze $s$ als Quelle, $t$ als Senke und die Kapazität jeder Kante \emph{und jedes Knotens} auf 1.
+		\item Der maximale Fluss entspricht der unterschiedlichen Pfade ohne gemeinsame Knoten.
+	\end{enumerate}
+	\item \textbf{Min-Cut}\newline
+	Der maximale Fluss ist gleich dem minimalen Schnitt.
+	Bei Quelle $s$ und Senke $t$, partitioniere in $S$ und $T$.
+	Zu $S$ gehören alle Knoten, die im Residualgraphen von $s$ aus erreichbar sind (Rückwärtskanten beachten).
+\end{itemize}
 
 \subsection{Min-Cost-Max-Flow}
 \lstinputlisting{graph/minCostMaxFlow.cpp}
-- 
cgit v1.2.3

