summaryrefslogtreecommitdiff
path: root/graph/graph.tex
diff options
context:
space:
mode:
authorPaul Jungeblut <paul.jungeblut@gmail.com>2016-10-06 22:31:06 +0200
committerPaul Jungeblut <paul.jungeblut@gmail.com>2016-10-06 22:31:06 +0200
commit66b9c77b34d376fcc7a23f8a6d98c7e8ba852ea2 (patch)
tree388d2873591fb98a537f91fcdce7693c0d33612a /graph/graph.tex
parent5de23397c83bb57067fbc1286d46f13cfa7a4de9 (diff)
Push Relabel space saving and fixing typos and sizing in flow section.
Diffstat (limited to 'graph/graph.tex')
-rw-r--r--graph/graph.tex12
1 files changed, 6 insertions, 6 deletions
diff --git a/graph/graph.tex b/graph/graph.tex
index ac8e92b..b14ebf4 100644
--- a/graph/graph.tex
+++ b/graph/graph.tex
@@ -74,18 +74,18 @@ Gut bei sehr dicht besetzten Graphen.
\lstinputlisting{graph/pushRelabel.cpp}
\subsubsection{Anwendungen}
-\begin{itemize}
+\begin{itemize}[nosep]
\item \textbf{Maximum Edge Disjoint Paths}\newline
Finde die maximale Anzahl Pfade von $s$ nach $t$, die keine Kante teilen.
- \begin{enumerate}
+ \begin{enumerate}[nosep]
\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.
+ \item Der maximale Fluss entspricht den unterschiedlichen Pfaden 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}
+ Finde die maximale Anzahl an Pfaden von $s$ nach $t$, die keinen Knoten teilen.
+ \begin{enumerate}[nosep]
\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.
+ \item Der maximale Fluss entspricht den unterschiedlichen Pfaden ohne gemeinsame Knoten.
\end{enumerate}
\item \textbf{Min-Cut}\newline
Der maximale Fluss ist gleich dem minimalen Schnitt.