Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
Download

📚 The CoCalc Library - books, templates and other resources

132928 views
License: OTHER
Tweet
Share
Share
1
\section{Minimale Spannbäume}

2


3
\subsection{Wozu minimale Spannbäume?}

4
\begin{frame}{Wozu?}{Why?}

5
	\only<1>{\includegraphics[scale=0.35]{Material/minSpannbaum_1.png}}

6
	\only<2>{\includegraphics[scale=0.35]{Material/minSpannbaum_2.png}}

7
	\only<3>{\includegraphics[scale=0.35]{Material/minSpannbaum_3.png}}

8
	\only<4>{\includegraphics[scale=0.35]{Material/minSpannbaum_4.png}}

9
	\only<5>{\includegraphics[scale=0.35]{Material/minSpannbaum_5.png}}

10
\end{frame}

11


12
\subsection{Was ist ein minimaler Spannbaum?}

13
\begin{frame}{Definition}

14
Minimale Spannbäume sind Teilgraphen, sodass ...

15
	\begin{itemize}

16
		\item ... alle Knoten erreichbar sind \pause

17
		\item ... die Summe der Kantengewichte minimal ist \pause

18
		\item ... kein Zyklus im Graph enthalten ist ($\Rightarrow$ Baum).

19
	\end{itemize}

20
\end{frame}

21


22
\begin{frame}{Definition}

23
	Sei	$G = (V, E) $ mit Kostenfunktion $w: E \rightarrow \mathbb{R}$

24
	\vspace{10 mm}

25


26
	$MST = (V, T)$ ist Spannbaum von G, wenn

27
	\begin{itemize}

28
		\item $T \subseteq E$ bzw.

29
		\item $ \forall u, v \in V: \exists$ Pfad von $u$ nach $v$

30
		\item $W(T) := \displaystyle\sum\limits_{(u, v) \in T} w(u, v)$ minimal ist.

31
	\end{itemize}

32


33
\end{frame}

34


35
\begin{frame}{Eindeutigkeit von Spannbäumen}{Ambiguity of minimal spanning trees}

36
	Ist dieser Spannbaum eindeutig? \only<2>{Nein}

37
	\only<1>{\includegraphics[scale=0.35]{Material/minSpannbaum_5.png}}

38
	\only<2>{\includegraphics[scale=0.35]{Material/minSpannbaum_amb.png}}

39
\end{frame}

40


41
\input{PrimsAlgorithm}     % Algorithmus von Prim

42


43
\input{KruskalsAlgorithm}  % Algorithmus von Kruskal

44