\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe},
  Thematik = {Prim nach Adjazenzmatrix, Tripelnotation},
  Referenz = 46115-2018-F.T1-A8,
  RelativerPfad = Examen/46115/2018/03/Thema-1/Aufgabe-8.tex,
  ZitatSchluessel = examen:46115:2018:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Prim, Algorithmus von Kruskal},
  EinzelpruefungsNr = 46115,
  Jahr = 2018,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 8,
}

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

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

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

\begin{enumerate}
\item 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 Sie sein Gewicht an.

\begin{bAntwort}
Der Graph muss nicht gezeichnet werden. Der Algorithmus kann auch nur
mit der Adjazenzmatrix durchgeführt werden. Möglicherweise geht das
Lösen der Aufgabe schneller mit der Matrix von der Hand.

\bPseudoUeberschrift{Kompletter Graph}

\begin{center}
\begin{tikzpicture}[li graph]
\node (s) at (0,-3) {s};
\node (a) at (2,0) {a};
\node (b) at (0,3) {b};
\node (c) at (2,2) {c};
\node (d) at (2,-2) {d};
\node (e) at (6,-3) {e};
\node (f) at (6,3) {f};
\node (g) at (6,1) {g};
\node (h) at (6,-1) {h};

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

\bPseudoUeberschrift{Tabelle schwarz-graue-Knoten}

\begin{tabular}{ll}
\bf{schwarze} & \bf{graue} \\
\hline
(s, null, -) & (b, s, 3); (e, s, 7);  \\
(b, s, 3) & (d, b, 5); (e, s, 7); (f, b, 10);  \\
(d, b, 5) & (a, d, 8); (e, d, 2); (f, d, 3); (h, d, 6);  \\
(e, d, 2) & (a, d, 8); (f, d, 3); (h, d, 6);  \\
(f, d, 3) & (a, d, 8); (c, f, 1); (g, f, 7); (h, d, 6);  \\
(c, f, 1) & (a, c, 0); (g, f, 7); (h, d, 6);  \\
(a, c, 0) & (g, f, 7); (h, d, 6);  \\
(h, d, 6) & (g, h, 4);  \\
(g, h, 4) &   \\
\end{tabular}

\bigskip

Gewicht des minimalen Spannbaums: 24

\bPseudoUeberschrift{Minimaler Spannbaum}

\begin{center}
\begin{tikzpicture}[li graph]
\node (s) at (0,-3) {s};
\node (a) at (2,0) {a};
\node (b) at (0,3) {b};
\node (c) at (2,2) {c};
\node (d) at (2,-2) {d};
\node (e) at (6,-3) {e};
\node (f) at (6,3) {f};
\node (g) at (6,1) {g};
\node (h) at (6,-1) {h};

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

%%
% (b)
%%

\item Welche Worst-Case-Laufzeitkomplexität hat der Algorithmus von
Prim, wenn die grauen Knoten in einem Heap 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}(m + n \log n)$
\end{bAntwort}

%%
% (c)
%%

\item Beschreiben Sie kurz die Idee des alternativen Ansatzes zur
Berechnung eines minimalen Spannbaumes von Kruskal.
\index{Algorithmus von Kruskal}

\begin{bAntwort}
Kruskal wählt nicht die kürzeste an einen Teilgraphen anschließende
Kante, sondern global die kürzeste verbliebene aller Kanten, die keinen
Zyklus bildet, ohne dass diese mit dem Teilgraph verbunden sein muss.
\end{bAntwort}

\end{enumerate}
\end{document}