\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Programmierung II - Übungsblatt 11 \\
	Übungsgruppe Do 14-16 \\	
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941) \\
	Andreas Glitsch (Matrikelnummer 2026130)}
\date{}

\maketitle

\newpage
\section*{Aufgabe 3}
{\bfseries Adjazenz-Liste:}
\begin{enumerate}[1.]
	\item Starte bei einem beliebigen Knoten $x$. \hfill $\OnotO(1)$
	\item Gehe die Liste der von $x$ erreichbaren Knoten durch und zähle die erreichbaren Knoten. \hfill $\OnotO(n)$
	\item Sind genau zwei Knoten erreichbar, wird $x$ in den Graphen $G^2$ aufgenommen. \hfill $\OnotO(1)$
	\item Gehe weiter zum nächsten Knoten und wiederhole Schritt 2. Sind keine Knoten mehr da, beende. \hfill $\OnotO(1)$
\end{enumerate}
Sei $m$ die Anzahl der Knoten. Dann ist die Gesamtlaufzeit in $\OnotO(m \cdot n)$. \\[0.8cm]
{\bfseries Adjazenz-Matrix:}
\begin{enumerate}[1.]
	\item Starte bei einem beliebigen Knoten $x$. \hfill $\OnotO(1)$
	\item Prüfe, ob $x$ mit einem anderen Knoten $y$ verbunden ist. \hfill $\OnotO(1)$
	\item Ist $x$ mit $y$ verbunden, prüfe, ob $y$ mit einem anderen Knoten $z$ verbunden ist; \\ sonst gehe weiter zum nächsten Knoten und wiederhole Schritt 2. \hfill $\OnotO(1)$
	\item Ist $y$ mit $z$ verbunden wird $y$ in $G^2$ aufgenommen. \hfill $\OnotO(1)$
	\item Gehe weiter zum nächsten Knoten und wiederhole Schritt 2. Sind keine Knoten mehr da, beende. \hfill $\OnotO(1)$
\end{enumerate}
Sei $m$ die Anzahl der Knoten. Dann ist die Gesamtlaufzeit in $\OnotO(m)$.

\end{document}
