23 lines
758 B
TeX
23 lines
758 B
TeX
\section{Kleinste Schnitte}
|
|
\begin{tasks}
|
|
\item
|
|
Siehe \autoref{fig:1a}.
|
|
\points{2}
|
|
|
|
\begin{figure}
|
|
\centering
|
|
\includegraphics[page=1, width=0.5\textwidth]{figures.pdf}
|
|
\caption{Gegenbeispiel; Minimaler Schnitt $\tup{S, T}$ und nicht minimaler Schnitt $\tup{\set{v}, V \setminus \set{v}}$ in rot.}
|
|
\label{fig:1a}
|
|
|
|
\end{figure}
|
|
|
|
\item
|
|
Die Wahrscheinlichkeit, dass \alg*{Contract} in keiner Iteration
|
|
eine Kante aus $C = \set{uv \in E \mid u \in S, v \in T}$ mit minimalem Schnitt $\tup{S, T}$ kontrahiert, also immer die falschen Knoten auswählt,
|
|
ist laut Vorlesung $\frac{2}{n(n-1)}$. Das heißt die Zahl der
|
|
richtigen Knoten wächst quadratisch, da die Wahrscheinlichkeit quadratisch
|
|
abnimmt.
|
|
\points{3}
|
|
|
|
\end{tasks}
|