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

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{bis zum 27. Januar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\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}}



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


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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Boris Klemz

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM\\
Dies ist das vorletzte regul\"are Aufgabenblatt.

\vskip 0.5cm

\begin{description}

\AUFGABE{Netzwerkfluss}{10 Punkte}

Betrachten Sie das folgende Flussnetzwerk $G$.
\begin{center}
\includegraphics{fluss}
\end{center}
Benutzen Sie den Algorithmus von Ford und Fulkerson,
um einen Maximum-Fluss von $S$ nach $T$ und 
einen Minimum-$S$-$T$-Schnitt in $G$ zu finden.
Zeigen Sie die einzelnen Schritte.

\AUFGABE {Fl\"usse, Paarungen, Knoten\"uberdeckungen}{10 Punkte}

\begin{enumerate}
\item Sei $G$ ein Flussnetzwerk, in dem alle
  Kapazit\"aten ganzzahlig  sind. Beweisen Sie: es existiert
  ein Maximum-Fluss $f^*$ f\"ur $G$, der nur ganzzahlige Werte annimmt. 
  Zeigen Sie auch, dass man $f^*$ in Polynomialzeit berechnen kann.
\item Sei $H = (V,E)$ ein ungerichteter bipartiter Graph. 
  Eine \emph{Paarung}
  in $H$ ist eine Menge $M \subseteq E$, so dass keine zwei Kanten
  in $M$ einen gemeinsamen Endpunkt haben. Geben Sie einen effizienten 
  Algorithmus an, der eine gr\"o\ss{}tm\"ogliche Paarung in $H$ bestimmt.
  Was ist die Laufzeit?

  \emph{Hinweis}: Definieren Sie ein geeignetes Flussnetzwerk und 
  benutzen Sie (a).

\item Sei $H = (V, E)$ ein ungerichteter bipartiter Graph. Eine 
 \emph{Knoten\"uberdeckung} f\"ur $H$ ist eine Menge $C \subseteq V$
 von Knoten, so dass jede Kante $e \in E$ zu mindestens einem Knoten in
 $C$ inzident ist. Geben Sie einen effizienten Algorithmus an, der 
 eine kleinstm\"ogliche 
 Knoten\"uberdeckung f\"ur $H$ findet.

  \emph{Hinweis}: Benutzen Sie Ihr Flussnetzwerk aus (b) und finden 
  Sie einen Zusammenhang zwischen Schnitten und Knoten\"uberdeckungen.
\end{enumerate}


\AUFGABE{Kantenzusammenhang}{10 Punkte}

Der \emph{Kantenzusammenhang} eines ungerichteten Graphen $G = (V,E)$
ist die kleinste Zahl $k$ an Kanten, die entfernt werden m\"ussen, damit
$G$ nicht zusammenh\"angend ist.

Zeigen Sie, dass man den Kantenzusammenhang von $G$ durch Berechnung der 
maximalen Fl\"usse in h\"ochstens $|V|$ Netzen mit jeweils $O(|V|)$ Knoten
und $O(|E|)$ Kanten bestimmen kann.
\end{description}

\end{document}
