diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/graph.tex | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/graph/graph.tex b/graph/graph.tex index bf23c5b..79404d4 100644 --- a/graph/graph.tex +++ b/graph/graph.tex @@ -1,7 +1,11 @@ \section{Graphen} -\subsection{Lowest Common Ancestor} -\lstinputlisting{graph/LCA.cpp} +\subsection{Minimale Spannbäume} +Benutze Algorithmus von \textsc{Kruskal} oder Algorithmus von \textsc{Prim}. +\begin{description} + \item[Schnitteigenschaft] Für jeden Schnitt $C$ im Graphen gilt: Gibt es eine Kante $e$, die echt leichter ist als alle anderen Schnittkanten, so gehört diese zu allen minimalen Spannbäumen. ($\Rightarrow$ Die leichteste Kante in einem Schnitt kann in einem minimalen Spannbaum verwendet werden.) + \item[Kreiseigenschaft] Für jeden Kreis $K$ im Graphen gilt: Die schwerste Kante auf dem Kreis ist nicht Teil des minimalen Spannbaums. +\end{description} \subsection{Kürzeste Wege} @@ -42,5 +46,23 @@ VISIT(v): \end{figure} \lstinputlisting{graph/euler.cpp} +\subsection{Lowest Common Ancestor} +\lstinputlisting{graph/LCA.cpp} + \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} + |