\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph,spalten}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Kürzeste-Wege-Bäume und minimale Spannbäume},
  Referenz = 66115-2021-F.T1-TA2-A4,
  RelativerPfad = Examen/66115/2021/03/Thema-1/Teilaufgabe-2/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2021:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Graphen, Algorithmus von Dijkstra, Algorithmus von Prim},
  EinzelpruefungsNr = 66115,
  Jahr = 2021,
  Monat = 03,
  ThemaNr = 1,
  TeilaufgabeNr = 2,
  AufgabeNr = 4,
}

Die Algorithmen von Dijkstra und Jarník-Prim gehen ähnlich
vor.\index{Graphen}\footcite{examen:66115:2021:03} Beide berechnen,
ausgehend von einem Startknoten, einen Baum. Allerdings berechnet der
Algorithmus von Dijkstra\index{Algorithmus von Dijkstra} einen
Kürzesten-Wege-Baum, während der Algorithmus von
Jarník-Prim\index{Algorithmus von Prim} einen minimalen Spannbaum
berechnet.

\begin{enumerate}

%%
% a)
%%

\item Geben Sie einen ungerichteten gewichteten Graphen $G$ mit
höchstens fünf Knoten und einen Startknoten $s$ von $G$ an, so dass
\textbf{Dijkstra}($G$, $s$) und \textbf{Jarník-Prim}($G$, $s$) ausgehend
von $s$ verschiedene Bäume in $G$ liefern. Geben Sie beide Bäume an.

\begin{bGraphenFormat}
A: 0 0
B: 1 1
S: 2 0
C: 1 -1
A -- B: 1
A -- C: 1
A -- S: 2
B -- S: 2
C -- S: 2
\end{bGraphenFormat}

\begin{bAntwort}
\begin{multicols}{2}
\bPseudoUeberschrift{Originalgraph}

\begin{tikzpicture}[li graph]
\node (A) at (0,0) {A};
\node (B) at (1,1) {B};
\node (C) at (1,-1) {C};
\node (S) at (2,0) {S};

\path (A) edge node {1} (B);
\path (A) edge node {1} (C);
\path (A) edge node {2} (S);
\path (B) edge node {2} (S);
\path (C) edge node {2} (S);
\end{tikzpicture}

\bPseudoUeberschrift{Dijkstra-Wegebaum von S aus:}

\begin{tikzpicture}[li graph]
\node (A) at (0,0) {A};
\node (B) at (1,1) {B};
\node (C) at (1,-1) {C};
\node (S) at (2,0) {S};

\path (A) edge node {2} (S);
\path (B) edge node {2} (S);
\path (C) edge node {2} (S);
\end{tikzpicture}

\columnbreak

\bPseudoUeberschrift{Minimaler Spannbaum 1}

\begin{tikzpicture}[li graph]
\node (A) at (0,0) {A};
\node (B) at (1,1) {B};
\node (C) at (1,-1) {C};
\node (S) at (2,0) {S};

\path (A) edge node {1} (B);
\path (A) edge node {1} (C);
\path (A) edge node {2} (S);
\end{tikzpicture}

\bPseudoUeberschrift{Minimaler Spannbaum 2}

\begin{tikzpicture}[li graph]
\node (A) at (0,0) {A};
\node (B) at (1,1) {B};
\node (C) at (1,-1) {C};
\node (S) at (2,0) {S};

\path (A) edge node {1} (B);
\path (A) edge node {1} (C);
\path (B) edge node {2} (S);
\end{tikzpicture}

\bPseudoUeberschrift{Minimaler Spannbaum 3}

\begin{tikzpicture}[li graph]
\node (A) at (0,0) {A};
\node (B) at (1,1) {B};
\node (C) at (1,-1) {C};
\node (S) at (2,0) {S};

\path (A) edge node {1} (B);
\path (A) edge node {1} (C);
\path (C) edge node {2} (S);
\end{tikzpicture}
\end{multicols}
\end{bAntwort}

%%
% b)
%%

\item Geben Sie eine unendlich große Menge von Graphen an, auf denen der
Algorithmus von Jarník-Prim asymptotisch schneller ist als der
Algorithmus von Kruskal, der ebenfalls minimale Spannbäume berechnet.

\emph{Hinweis:} Für einen Graphen mit $n$ Knoten und $m$ Kanten benötigt
Jarník-Prim $\mathcal{O}(m + n \log n)$ Zeit, Kruskal $\mathcal{O}(m
\log m)$ Zeit.

%%
% c)
%%

\item Sei $Z$ die Menge der zusammenhängenden Graphen und $G \in Z$. Sei
$n$ die Anzahl der Knoten von $G$ und $m$ die Anzahl der Kanten von $G$.
Entscheiden Sie mit Begründung, ob $\log m \in \Theta(\log n)$ gilt.

\end{enumerate}
\end{document}