From ecd1b477293e00749d5281a3b42f17f4b00030dc Mon Sep 17 00:00:00 2001 From: Paul Jungeblut Date: Tue, 25 Nov 2014 10:41:59 +0100 Subject: Schnitteigenschaft/Kreiseigenschaft --- graph/graph.tex | 11 +++++++++-- tcr.pdf | Bin 168187 -> 169776 bytes toDo.txt | 2 +- 3 files changed, 10 insertions(+), 3 deletions(-) diff --git a/graph/graph.tex b/graph/graph.tex index d90c346..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,6 +46,9 @@ 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} diff --git a/tcr.pdf b/tcr.pdf index 0981a42..5becf6a 100644 Binary files a/tcr.pdf and b/tcr.pdf differ diff --git a/toDo.txt b/toDo.txt index e879d8e..e97a4fc 100644 --- a/toDo.txt +++ b/toDo.txt @@ -7,4 +7,4 @@ - linear time sorting - roman numerals - towers of hanoi -- Schnitteigenschaft/Kreiseigenschaft \ No newline at end of file +- NIM GAMES (WICHTIG) \ No newline at end of file -- cgit v1.2.3