diff options
| author | Paul Jungeblut <s_jungeb@i08pc56.atis-stud.uni-karlsruhe.de> | 2014-11-25 10:29:35 +0100 |
|---|---|---|
| committer | Paul Jungeblut <s_jungeb@i08pc56.atis-stud.uni-karlsruhe.de> | 2014-11-25 10:29:35 +0100 |
| commit | e3695db184df02edbe155b58a9cba7f6cf5d337b (patch) | |
| tree | ed18d2ba4cebf8d75bfcff84061846c8393aedc2 /graph/graph.tex | |
| parent | 9132c2f869e166f871027a99d1746f712397ce08 (diff) | |
some max flow comments
Diffstat (limited to 'graph/graph.tex')
| -rw-r--r-- | graph/graph.tex | 15 |
1 files changed, 15 insertions, 0 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index bf23c5b..d90c346 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -44,3 +44,18 @@ VISIT(v): \subsection{Max-Flow (\textsc{Edmonds-Karp}-Algorithmus)} \lstinputlisting{graph/edmondsKarp.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} + |