\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 5.\@ Mai 2015 vor der Vorlesung in die
Mitarbeiterschachteln}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung \hfill SoSe 2015

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Der Algorithmus von Floyd-Rivest}{10 Punkte}

Passen Sie den Algorithmus von Floyd und Rivest so an,
dass er das folgende Problem l\"ost:
gegeben ein unsortiertes Array $A$ mit $n$ Elementen
aus einem total geordneten Universum und $k \in \{1, \dots, n/2\}$, finde
das Element $a \in A$ mit $\text{rg}_A(a) = k$ in $n + k + o(n)$
Vergleichen im Erwartungswert.

\AUFGABE{Der Algorithmus von Bor\r{u}vka}{10 Punkte}


Sei $G =(V, E)$ ein zusammenh\"angender ungerichteter gewichteter Graph mit
$n$ Knoten und $m$ Kanten. Ohne Einschr\"ankung der Allgemeinheit seien
alle Kantengewichte paarweise verschieden.

Der \emph{Algorithmus von Bor\r{u}vka} zur Berechnung eines minimalen
aufspannenden Baumes (MST) besteht aus einer Folge von \emph{Bor\r{u}vka-Phasen}.
In jeder Phase w\"ahlt jeder Knoten die inzidente Kante mit geringstem Gewicht.
Die resultierende Kantenmenge $F$ induziert einen aufspannenden Wald von $G$.
Die Komponenten dieses Waldes werden kontrahiert, Schleifen werden gel\"oscht,
von Mehrfachkanten werden nur die Kanten geringsten Gewichts behalten. 
Der Algorithmus ist beendet, sobald der aktuelle Graph nur noch aus einem einzigen
Knoten besteht. Das Ergebnis ist die Vereinigung aller Kantenmengen, die im Laufe
der Ausf\"uhrung kontrahiert wurden.

\begin{enumerate}
\item Zeigen Sie, dass der Algorithmus von Bor\r{u}vka einen MST
  berechnet.
\item Zeigen Sie, dass sich eine Bor\r{u}vka-Phase in Zeit $O(m')$ implementieren
  l\"asst, wobei $m'$ die Anzahl der Kanten im aktuellen Graphen bezeichnet.
\item Folgern Sie, dass der Algorithmus  $O(\min\{m \log n, n^2\})$
  Schritte ben\"otigt.
\item Erinnern Sie sich, dass der Algorithmus von Prim einen MST von $G$
  in Zeit $O(n \log n + m)$ berechnen kann. Kombinieren Sie den Algorithmus
  von Prim mit dem Algorithmus von Bor\r{u}vka, um einen Algorithmus zu
  erhalten, der $\text{MST}(G)$ in $O(m \log\log n)$ Schritten berechnet.

  \emph{Hinweis}: F\"uhren Sie erst eine geeignete Anzahl von Bor\r{u}vka-Phasen
    durch, und wechseln Sie dann zu Prim.
\end{enumerate}

\AUFGABE{MST-\"Uberpr\"ufung} {10 Punkte}

Sei wieder $G =(V, E)$ ein zusammenh\"angender ungerichteter gewichteter Graph mit
$n$ Knoten und $m$ Kanten, wobei alle Kantengewichte paarweise verschieden sind.

Sei $A \subseteq E$ kreisfrei. Eine Kante $e \in E$ hei\ss{}t \emph{$A$-leicht},
wenn (i) $A \cup \{e\}$ kreisfrei ist oder (ii) der eindeutige Kreis $C$ in 
$A \cup \{e\}$ eine Kante enth\"alt, die schwerer ist als $e$.

\begin{enumerate}
  \item  Beweisen Sie, dass $A$ genau dann ein 
    minimaler aufspannender Baum von $G$ ist, wenn $E \setminus A$ keine
    $A$-leichten Kanten enth\"alt.
  \item  Beweisen Sie, dass $e \in E$ genau dann
    $A$-leicht ist, wenn $e \in \text{MSF}(A \cup \{e\})$ ist,
    wobei $\text{MSF}$ den minimalen aufspannenden \emph{Wald}
    bezeichne.
\end{enumerate}

\end{description}
\end{document}
