Adding a push relabel max flow algorithm to the TCR.

1 files changed, 24 insertions, 13 deletions

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}