From ecd1b477293e00749d5281a3b42f17f4b00030dc Mon Sep 17 00:00:00 2001
From: Paul Jungeblut <s_jungeb@i08pc56.atis-stud.uni-karlsruhe.de>
Date: Tue, 25 Nov 2014 10:41:59 +0100
Subject: Schnitteigenschaft/Kreiseigenschaft

---
 graph/graph.tex | 11 +++++++++--
 1 file changed, 9 insertions(+), 2 deletions(-)

(limited to 'graph/graph.tex')

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}
 
-- 
cgit v1.2.3

