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

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{am 19. Juli 2016 bis 12 Uhr in die
Tutorenf\"acher}

\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{\N}{\mathbb{N}}
\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{Informatik B}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM
\\
Dies ist ein freiwilliges Zusatzblatt.

\vskip 0.5cm


\begin{description}

\AUFGABE{Breitensuche, Tiefensuche und Dijkstras Algorithmus}{10 Zusatzpunkte}

\begin{enumerate}
\item F\"uhren Sie in dem folgenden Graphen eine Breitensuche und eine Tiefensuche
aus, ausgehend vom Startknoten $s$. Gehen Sie davon aus, dass die Adjazenzlisten
in alphabetischer Reihenfolge sortiert sind. Zeigen Sie die einzelnen Schritte.
\begin{center}
\includegraphics{u12_graph.pdf}
\end{center}
\item
Benutzen Sie im folgenden Graphen den Algorithmus von Dijkstra, 
um den k\"urzesten-Wege-Baum f\"ur $s$ zu bestimmen.
Gehen Sie davon aus, dass die Adjazenzlisten
in alphabetischer Reihenfolge sortiert sind. Zeigen Sie die einzelnen Schritte.
\begin{center}
\includegraphics{u12_graph2.pdf}
\end{center}

\item Geben Sie ein Beispiel daf\"ur, dass Dijkstras Algorithmus
   nicht notwendigerweise die richtige Antwort liefert, falls
   negative Kantengewichte erlaubt sind. Ihr Beispielgraph soll
   keine negativen Kreise enthalten.
\end{enumerate}


\AUFGABE{Graphen mit einem Kreis}{10 Zusatzpunkte}

Im Folgenden sollen zwei Kreise in einem ungerichteten Graphen als gleich angesehen
werden, wenn sie die gleichen Knoten und Kanten haben, sich also nur durch Wahl des
Anfangspunktes oder der Umlaufrichtung unterscheiden.
\begin{enumerate}
\item
Zeigen Sie, dass f\"ur einen zusammenh\"angenden ungerichteten
Graphen $G = (V, E)$ die folgende
\"Aquivalenz gilt: 
\[
\text{$G$ hat genau einen Kreis} \quad \Leftrightarrow \quad |E| = |V|.
\]

\emph{Hinweis}: Unterteilen Sie den Beweis in zwei Teilschritte
\begin{align*}
\text{$G$ hat (mindestens) einen Kreis} &\Leftrightarrow   |E| \geq |V|, \text{ und}\\
\text{$G$ hat h\"ochstens einen Kreis} &\Leftrightarrow  |E| \leq |V|.
\end{align*}
\item Beschreiben Sie verbal einen Algorithmus, der f\"ur einen beliebigen ungerichteten
Graphen $G = (V, E)$ entscheidet, ob er genau einen Kreis enth\"alt. Sie k\"onnen und
sollten dazu Algorithmen aus der Vorlesung als Hilfsfunktionen verwenden.
\end{enumerate}
\AUFGABE{Vermischtes}{10 Zusatzpunkte}
\begin{enumerate}
\item
Was versteht man in Java unter dem Begriff \emph{overriding} von Methoden?
Geben Sie ein kurzes Beispiel.
\item Richtig oder falsch? In jedem schlichten ungerichteten Graphen $G = (V,E)$ mit $n$ Knoten 
gilt: Ist $f(n) = \Theta(\log |V|)$, so ist auch $f(n) = \Theta(\log |E|)$.
Was passiert, wenn wir zus\"atzlich annehmen, dass $G$ zusammenh\"angend ist?

Begr\"unden Sie Ihre Antworten.
\item Sei $k \in \N$ eine Konstante und seien $f_1, \dots, f_k, h: \N \rightarrow \N$ Funktionen, 
so dass f\"ur $i \in \{1, \dots, k\}$ gilt: $f_i(n) = O(h(n))$. Beweisen Sie anhand der Definitionen, dass 
dann auch $f_1(n) + \dots + f_k(n) = O(h(n))$ ist.
\item
Richtig oder Falsch: Jeder AVL-Baum ist auch ein bin\"arer Heap. 

Begr\"unden Sie Ihre Antwort.
\end{enumerate}
\end{description}
\end{document}
