\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 10},
  Thematik = {Graph a-h},
  Referenz = 66115-2018-F.T2-A10,
  RelativerPfad = Examen/66115/2018/03/Thema-2/Aufgabe-10.tex,
  ZitatSchluessel = examen:66115:2018:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Prim},
  EinzelpruefungsNr = 66115,
  Jahr = 2018,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 10,
}

\begin{enumerate}

%%
% a)
%%

\item Berechnen Sie mithilfe des Algorithmus von Prim ausgehend vom
Knoten $a$ einen minimalen Spannbaum des ungerichteten Graphen $G$, der
durch folgende Adjazenzmatrix gegeben ist:
\index{Algorithmus von Prim}
\footcite{examen:66115:2018:03}

% Info_2021-06-18-2021-06-18_13.18.21.mp4
% 2h06m

\begin{bGraphenFormat}
a: 0 -1
b: 10 -1
c: 4 0
d: 6 3
e: 8 1
f: 6 1
g: 10 4
h: 0 4
a -- b: 1
a -- c: 4
a -- d: 6
a -- h: 5
b -- c: 3
b -- e: 4
b -- g: 7
c -- d: 1
d -- e: 9
d -- f: 6
d -- g: 2
d -- h: 0
e -- f: 5
e -- g: 5
g -- h: 8
h -- h: 1
\end{bGraphenFormat}

\[
\begin{blockarray}{ccccccccc}
   & a & b & c & d & e & f & g & h \\
\begin{block}{c(cccccccc)}
 a & * & 1 & 4 & 6 & - & - & - & 5 \\
 b & 1 & * & 3 & - & 4 & - & 7 & - \\
 c & 4 & 3 & * & 1 & - & - & - & - \\
 d & 6 & - & 1 & * & 9 & 6 & 2 & 0 \\
 e & - & 4 & - & 9 & * & 5 & 5 & - \\
 f & - & - & - & 6 & 5 & * & - & - \\
 g & - & 7 & - & 2 & 5 & - & * & 8 \\
 h & 5 & - & - & 0 & - & - & 8 & 1 \\
\end{block}
\end{blockarray}
\]

\begin{center}
\begin{tikzpicture}[li graph,every loop/.style={}]
\node (a) at (0,-1) {a};
\node (b) at (10,-1) {b};
\node (c) at (4,0) {c};
\node (d) at (6,3) {d};
\node (e) at (8,1) {e};
\node (f) at (6,1) {f};
\node (g) at (10,4) {g};
\node (h) at (0,4) {h};

\path (a) edge node {1} (b);
\path (a) edge node {4} (c);
\path (a) edge node {6} (d);
\path (a) edge node {5} (h);
\path (b) edge node {3} (c);
\path (b) edge node {4} (e);
\path (b) edge node {7} (g);
\path (c) edge node {1} (d);
\path (d) edge node {9} (e);
\path (d) edge node {6} (f);
\path (d) edge node {2} (g);
\path (d) edge node {0} (h);
\path (e) edge node {5} (f);
\path (e) edge node {5} (g);
\path (g) edge node {8} (h);
\path (h) edge[loop above] node {1} (h);
\end{tikzpicture}
\end{center}

Erstellen Sie dazu eine Tabelle mit zwei Spalten und stellen Sie jeden
einzelnen Schritt des Verfahrens in einer eigenen Zeile dar. Geben Sie
in der ersten Spalte denjenigen Knoten $v$, der vom Algorithmus als
nächstes in den Ergebnisbaum aufgenommen wird (dieser sog.
„schwarze“ Knoten ist damit fertiggestellt), als Tripel $(v, p, \delta)$
mit $v$ als Knotenname, $p$ als aktueller Vorgängerknoten und $\delta$
als aktuelle Distanz von $v$ zu $p$ an. Führen Sie in der zweiten Spalte
alle anderen vom aktuellen Spannbaum direkt erreichbaren Knoten $v$
(sog. „graue Randknoten“) ebenfalls als Tripel $(v, p, \delta)$ auf.

Zeichnen Sie anschließend den entstandenen Spannbaum und geben sein
Gewicht an.

\begin{bAntwort}

\begin{tabular}{l|l}
„schwarze“ & „graue“ Randknoten \\\hline\hline
(a, NULL, $\infty$) & (b, a, 1) (c, a, 4)  (h, a, 5) (d, a, 6) \\\hline
(b, a, 1) & (c, b, 3) (e, b, 4) (h, a, 5) (d, a, 6) (g, b, 7) \\\hline
(c, b, 3) & (d, c, 1) (e, b, 4) (h, a, 5) (g, b, 7) \\\hline
(d, c, 1) & (h, d, 0) (g, d, 2) (e, b, 4) (f, d, 6)\\\hline
(h, d, 0) & (g, d, 2) (e, b, 4) (f, d, 6) \\\hline
(g, d, 2) & (e, b, 4) (f, d, 6) \\\hline
(e, b, 4) & (f, e, 5) \\\hline
(f, e, 5) & \\\hline
\end{tabular}

\begin{center}
\begin{tikzpicture}[li graph,x=0.8cm,y=0.8cm]
\node (a) at (0,-1) {a};
\node (b) at (10,-1) {b};
\node (c) at (4,0) {c};
\node (d) at (6,3) {d};
\node (e) at (8,1) {e};
\node (f) at (6,1) {f};
\node (g) at (10,4) {g};
\node (h) at (0,4) {h};

\path (a) edge node {1} (b);
% \path (a) edge node {4} (c);
% \path (a) edge node {6} (d);
% \path (a) edge node {5} (h);
\path (b) edge node {3} (c);
\path (b) edge node {4} (e);
% \path (b) edge node {7} (g);
\path (c) edge node {1} (d);
% \path (d) edge node {9} (e);
% \path (d) edge node {6} (f);
\path (d) edge node {2} (g);
\path (d) edge node {0} (h);
\path (e) edge node {5} (f);
% \path (e) edge node {5} (g);
% \path (g) edge node {8} (h);
% \path (h) edge (h);
\end{tikzpicture}

\end{center}
Minimales Kantengewicht: 16
\end{bAntwort}

%%
% b)
%%

\item Welche Worst-Case-Laufzeitkomplexität hat der Algorithmus von
Prim, wenn die grauen Knoten in einem Heap (= Halde) nach Distanz
verwaltet werden? Sei dabei $n$ die Anzahl an Knoten und $m$ die Anzahl
an Kanten des Graphen. Eine Begründung ist nicht erforderlich.

\begin{bAntwort}
$\mathcal{O}(n \cdot \log(n) + m)$
\end{bAntwort}

%%
% c)
%%

\item Zeigen Sie durch ein kleines Beispiel, dass ein minimaler
Spannbaum eines ungerichteten Graphen nicht immer eindeutig ist.

\begin{bGraphenFormat}
a: 0 0
b: 2 2
c: 4 0
a -- b: 1
b -- c: 1
a -- c: 1
\end{bGraphenFormat}

\begin{bAntwort}
\begin{tikzpicture}[li graph]
\node (a) at (0,0) {a};
\node (b) at (1,1) {b};
\node (c) at (2,0) {c};

\path (a) edge node {1} (b);
\path (a) edge node {1} (c);
\path (b) edge node {1} (c);
\end{tikzpicture}
\hspace{0.5cm}
\begin{tikzpicture}[li graph]
\node (a) at (0,0) {a};
\node (b) at (1,1) {b};
\node (c) at (2,0) {c};

\path (a) edge node {1} (b);
\path (a) edge node {1} (c);
\end{tikzpicture}
\hspace{0.5cm}
\begin{tikzpicture}[li graph]
\node (a) at (0,0) {a};
\node (b) at (1,1) {b};
\node (c) at (2,0) {c};

\path (a) edge node {1} (b);
\path (b) edge node {1} (c);
\end{tikzpicture}
\end{bAntwort}

%%
% d)
%%

\item Skizzieren Sie eine Methode, mit der ein maximaler Spannbaum mit
einem beliebigen Algorithmus für minimale Spannbäume berechnet werden
kann. In welcher Laufzeitkomplexität kann ein maximaler Spannbaum
berechnet werden?

\begin{bAntwort}
Alle Kantengewichte negieren. In $\mathcal{O}(n \cdot \log(n) + m)$ wie
der Algorithmus von Prim.
\end{bAntwort}
\end{enumerate}
\end{document}