\documentclass{paper}

\setlength {\parindent} {0 pt}
\setlength {\parskip} {1.5 ex plus 0.5 ex minus 0.2 ex}

\usepackage{fullpage}
\usepackage {amssymb}
\usepackage {amsmath}
\usepackage {amsthm}
%\usepackage {wasysym}
\usepackage [usenames] {color}

\usepackage {enumerate}
\usepackage {cite}
\usepackage{float}
\usepackage {xspace}
\usepackage {ngerman}


\floatstyle{ruled}
\newfloat{algorithm}{thp}{alg}
\floatname{algorithm}{Algorithm}


%\usepackage {hyperref}

\newcommand {\mathset} [1] {\ensuremath {\mathbb {#1}}}
\newcommand {\R} {\mathset {R}}
\newcommand {\Q} {\mathset {Q}}
\newcommand {\Z} {\mathset {Z}}
\newcommand {\EX} {\mathbf {E}}
\newcommand {\script} [1] {\ensuremath {\mathcal {#1}}}
\newcommand {\etal} {\textit {et al.}}
\newcommand {\eps} {\varepsilon}
\newcommand {\eqdef} {:=}
\newcommand {\boruvka}{Bor\r{u}vka}
\newcommand {\wspd}{\texttt{wspd}}
\DeclareMathOperator{\emst}{emst}
\DeclareMathOperator{\conv}{CH}
\DeclareMathOperator{\argmin}{argmin}
\DeclareMathOperator{\DT}{DT}
\DeclareMathOperator{\UC}{UC}
\DeclareMathOperator{\LC}{LC}
\newcommand{\DKL}{D_\textup{KL}}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{problem}[theorem]{Problem}
\newtheorem{obs}[theorem]{Beobachtung}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{definition}[theorem]{Definition}


\title{Bor\r{u}vkas MST-Algorithmus}
\author{Wolfgang Mulzer}

\begin{document}
\maketitle

\section{Der Algorithmus}

\begin{itemize}
\item \textbf{Eingabe}: ein zusammenh\"angender gewichteter Graph $G = (V, E)$.
\item \textbf{Annahme}: alle Kantengewichte in $G$ sind paarweise verschieden.
\end{itemize}

\begin{verbatim}
// Initialisiere Kantenmenge des MST als leere Menge
A <- {}
while |A| < n-1 do
  B <- {}
  for each connected component C of (V,A) do
    find the lightest edge e with exactly one endpoint in C
    add e to B (if e is not in B yet) 
  add all edges in B to A
\end{verbatim}

\section{Analyse}

Jede Durchlauf der \texttt{while}-Schleife l\"asst sich in $O(|E|)$
Zeit implementieren: 
\begin{itemize}
  \item Benutze BFS in $(V,A)$, um die Zsh-Komponenten zu bestimmen,
    speichere mit jedem Knoten die Nummer seiner Zsh-Komponente.
    $O(|V| + |A|) = O(|E|)$ Zeit (da $|V|, |A| = O(|E|)$ sind).
  \item Speichere mit jeder Zsh-Komponente die leichteste inzidente
    Kante. Gehe alle Kanten durch, betrachte die beiden Zsh-Komponenten 
    inzident zu der aktuellen Kante, aktualisiere die leichteste Kante,
    falls n\"otig. $O(|E|)$ Zeit.
\end{itemize}

\begin{lemma}
 Nach dem $i$-ten Durchlauf der \texttt{while}-Schleife 
 haben alle Zsh-Komponenten mindestens  $2^i$ Knoten.
\end{lemma}
\begin{proof}[Beweis]
Induktion: vor dem ersten Durchlauf hat jede Komponente $1 = 2^0$ Knoten.
In jedem Durchlauf wird jede Zsh-Komponente mit mindestens einer anderen
Zsh-Komponente vereinigt, also verdoppelt sich die G\"o\ss{}e mindestens.
\end{proof}

Folglich gibt es nach $O(\log |V|)$ Durchl\"aufen nur noch eine Zsh-Komponente.
Die Laufzeit ist $O(|E|\log|V|)$.
\end{document}