diff options
| -rw-r--r-- | graph/graph.tex | 15 | ||||
| -rw-r--r-- | tcr.pdf | bin | 330156 -> 168187 bytes | |||
| -rw-r--r-- | tcr.tex | 10 | ||||
| -rw-r--r-- | toDo.txt | 3 |
4 files changed, 22 insertions, 6 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} + Binary files differ@@ -21,6 +21,7 @@ \chead{ChaosKITs} \ohead{\pagemark} +\usepackage{pxfonts} \usepackage{listings} \lstset{ language={C++}, @@ -32,14 +33,15 @@ breakautoindent=true, breakatwhitespace=false, postbreak=\space, - tabsize=2, + tabsize=4, basicstyle=\ttfamily\footnotesize, showspaces=false, showstringspaces=false, extendedchars=true, - keywordstyle=\color{blue}\bfseries, - stringstyle=\color{darkred}, - commentstyle=\color{darkgreen} + keywordstyle=\bfseries, + stringstyle=\bfseries, + commentstyle=\bfseries, + frame=trbl } \usepackage[top=2cm, bottom=2cm, left=2cm, right=1cm]{geometry} @@ -7,5 +7,4 @@ - linear time sorting - roman numerals - towers of hanoi -- Schnitteigenschaft/Kreiseigenschaft -- Zusammenhang Max Flow, Max Independent Set, etc.
\ No newline at end of file +- Schnitteigenschaft/Kreiseigenschaft
\ No newline at end of file |