\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 7},
  Thematik = {Kürzeste Kreise},
  Referenz = 66115-2012-F.T1-A7,
  RelativerPfad = Examen/66115/2012/03/Thema-1/Aufgabe-7.tex,
  ZitatSchluessel = examen:66115:2012:03,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Breitensuche},
  EinzelpruefungsNr = 66115,
  Jahr = 2012,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 7,
}

Mit der Länge eines Pfads oder eines Kreises bezeichnen wir die Anzahl
der Kanten, aus denen der Pfad bzw. der Kreis besteht. Bekanntlich kann
man Breitensuche verwenden, um für zwei gegebene Knoten s und ? die
Länge eines kürzesten s-t-Wegs zu berechnen. Im folgenden geht es um die
Berechnung kürzester Kreise.\index{Breitensuche}
\footcite{examen:66115:2012:03}

\begin{enumerate}

%%
% a)
%%

\item Für einen Graphen G und einen Knoten v von G berechnet KK(G,v)
(siehe Abbildung 1) die Länge des kürzesten Kreises in G, der durch v
geht.

Analysieren Sie die Laufzeit von KK in Abhängigkeit von der Anzahl n der
Knoten von G, von der Anzahl m der Kanten von G und vom Grad deg(v) des
übergebenen Knotens v.

%%
% b)
%%

\item Wenn man den Algorithmus KK für jeden Knoten eines Graphen G
aufruft, kann man die Länge eines kürzesten Kreises in G berechnen.
Welche Laufzeit hat der resultierende Algorithmus in in Abhängigkeit von
n und m?

%%
% c)
%%

\item Geben Sie einen Algorithmus KKschnell(G, v) an, der in O(n +m)
Zeit die Länge des kürzesten Kreises in G berechnet, der durch v geht.
Argumentieren Sie, warum ihr Algorithmus korrekt ist.
\end{enumerate}

Abbildung 1

vum pam aba ee aan mn a sr lee

KK(ungerichteter UNBEWICHLELEN rapı

ıL=
2 Adi): ={weV | {v,w} € E}
8 foreach w € Adjlvj do

4 | Sei G’ der Graph G ohne die Kante {v, w}.

5 Sei £ die Länge eines kürzesten v-w-Wegs in G’.
6 if 2< L then

7 | Lex

s return L

\end{document}