\documentclass{bschlangaul-aufgabe}
\bLadePakete{graph}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 10: Graphen I},
  Thematik = {drei Graphen G1, G2, G3},
  Referenz = 46115-2013-F.T2-A5,
  RelativerPfad = Examen/46115/2013/03/Thema-2/Aufgabe-5.tex,
  ZitatSchluessel = aud:pu:7,
  ZitatBeschreibung = {Aufgabe 10},
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Algorithmus von Dijkstra},
  EinzelpruefungsNr = 46115,
  Jahr = 2013,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 5,
}

\section{Aufgabe 10: Graphen I
\index{Algorithmus von Dijkstra}
\footcite[Aufgabe 10]{aud:pu:7}}

Gegeben seien folgende ungerichtete Graphen in textueller Notation,
wobei die erste Menge die Menge der Knoten und die zweite Menge die
Menge der Kanten ist:
\footcite[Thema 2 Aufgabe 5 (Auszug)]{examen:46115:2013:03}

$G_1 = ( \{1,2,3,4,5,6\}, \{[1,2], [1,4], [2,3], [3,4], [4,5], [4,6], [5,6]\} )$

$G_2 = ( \{1,2,3,4,5,6\}, \{[1,2], [1,3], [2,3], [4,5], [4,6], [5,6]\} )$

$G_3 = ( \{1,2,3,4,5,6\}, \{[1,2], [1,6], [2,3], [2,5], [3,4], [4,5], [5,6]\} )$

\begin{enumerate}

%%
% (a)
%%

\item Zeichnen Sie die obigen Graphen.

\begin{bAntwort}
\begin{itemize}

\item $G_1$

\begin{bGraphenFormat}
1: 0 0
2: 2 0
3: 4 1
4: 4 2
5: 3 3
6: 0 3
1 -- 2
1 -- 4
2 -- 3
3 -- 4
4 -- 5
4 -- 6
5 -- 6
\end{bGraphenFormat}

\begin{tikzpicture}[li graph]
\node (1) at (0,0) {1};
\node (2) at (2,0) {2};
\node (3) at (4,1) {3};
\node (4) at (4,2) {4};
\node (5) at (3,3) {5};
\node (6) at (0,3) {6};

\path (1) edge node {1} (2);
\path (1) edge node {1} (4);
\path (2) edge node {1} (3);
\path (3) edge node {1} (4);
\path (4) edge node {1} (5);
\path (4) edge node {1} (6);
\path (5) edge node {1} (6);
\end{tikzpicture}

\item $G_2$

\begin{bGraphenFormat}
1: 0 0
2: 2 0
3: 4 1
4: 4 2
5: 3 3
6: 0 3
1 -- 2
1 -- 3
2 -- 3
4 -- 5
4 -- 6
5 -- 6
\end{bGraphenFormat}

\begin{tikzpicture}[li graph]
\node (1) at (0,0) {1};
\node (2) at (2,0) {2};
\node (3) at (4,1) {3};
\node (4) at (4,2) {4};
\node (5) at (3,3) {5};
\node (6) at (0,3) {6};

\path (1) edge node {1} (2);
\path (1) edge node {1} (3);
\path (2) edge node {1} (3);
\path (4) edge node {1} (5);
\path (4) edge node {1} (6);
\path (5) edge node {1} (6);
\end{tikzpicture}

\item $G_3$

\begin{bGraphenFormat}
1: 0 0
2: 2 0
3: 4 1
4: 4 2
5: 3 3
6: 0 3
1 -- 2
1 -- 6
2 -- 3
2 -- 5
3 -- 4
4 -- 5
5 -- 6
\end{bGraphenFormat}

\begin{tikzpicture}[li graph]
\node (1) at (0,0) {1};
\node (2) at (2,0) {2};
\node (3) at (4,1) {3};
\node (4) at (4,2) {4};
\node (5) at (3,3) {5};
\node (6) at (0,3) {6};

\path (1) edge node {1} (2);
\path (1) edge node {1} (6);
\path (2) edge node {1} (3);
\path (2) edge node {1} (5);
\path (3) edge node {1} (4);
\path (4) edge node {1} (5);
\path (5) edge node {1} (6);
\end{tikzpicture}
\end{itemize}

\end{bAntwort}

%%
% (b)
%%

\item Erstellen Sie zu jedem Graphen die zugehörige Adjazenzmatrix mit
$X$ als Symbol für eine eingetragene Kante.

\begin{bAntwort}

\begin{itemize}

\item $G_1$

\begin{displaymath}
\begin{blockarray}{ccccccc}
  & 1 & 2 & 3 & 4 & 5 & 6 \\
\begin{block}{c(cccccc)}
1 & - & X &   & X &   &   \\
2 & X & - & X &   &   &   \\
3 &   & X & - & X &   &   \\
4 & X &   & X & - & X & X \\
5 &   &   &   & X & - & X \\
6 &   &   &   & X & X & - \\
\end{block}
\end{blockarray}
\end{displaymath}

\item $G_2$

\begin{displaymath}
\begin{blockarray}{ccccccc}
  & 1 & 2 & 3 & 4 & 5 & 6 \\
\begin{block}{c(cccccc)}
1 & - & X & X &   &   &   \\
2 & X & - & X &   &   &   \\
3 & X & X & - &   &   &   \\
4 &   &   &   & - & X & X \\
5 &   &   &   & X & - & X \\
6 &   &   &   & X & X & - \\
\end{block}
\end{blockarray}
\end{displaymath}

\item $G_3$

\begin{displaymath}
\begin{blockarray}{ccccccc}
  & 1 & 2 & 3 & 4 & 5 & 6 \\
\begin{block}{c(cccccc)}
1 & - & X &   &   & X & X \\
2 & X & - & X &   &   &   \\
3 &   & X & - & X &   &   \\
4 &   &   & X & - & X &   \\
5 &   & X &   & X & - & X \\
6 & X &   &   &   & X & - \\
\end{block}
\end{blockarray}
\end{displaymath}

\end{itemize}
\end{bAntwort}

%%
% (c)
%%

\item Betrachten Sie nun folgenden gerichteten Graphen $G_4$:

\begin{bGraphenFormat}
A: 1 2
B: 0 0
C: 0 4
D: 4 2
E: 5 4
F: 7 3.5
A -> B: 4
A -> C: 2
A -> D: 7
B -> D
C -> B: 2
C -> D: 4
D -> E
D -> F: 4
E -> F: 2
E -> C: 2
C -> E: 5
\end{bGraphenFormat}

\begin{tikzpicture}[li graph]
\node (A) at (1,2) {A};
\node (B) at (0,0) {B};
\node (C) at (0,4) {C};
\node (D) at (4,2) {D};
\node (E) at (5,4) {E};
\node (F) at (7,3.5) {F};

\path[->] (A) edge node {4} (B);
\path[->] (A) edge node {2} (C);
\path[->] (A) edge node {7} (D);
\path[->] (B) edge node {1} (D);
\path[->] (C) edge node {2} (B);
\path[->] (C) edge node {4} (D);
\path[->] (D) edge node {1} (E);
\path[->] (D) edge node {4} (F);
\path[->] (E) edge node {2} (F);
\path [->, bend angle=10, bend right] (C) edge node {5} (E);
\path [->, bend angle=10, bend right] (E) edge node {2} (C);
\end{tikzpicture}

Bestimmen Sie die kürzeste Entfernung von Knoten A zu jedem anderen
Knoten des Graphen. Verwenden Sie dazu den Algorithmus von Dijkstra und
tragen Sie Ihre einzelnen Rechenschritte in eine Tabelle folgender Form
ein (schreiben Sie neben jede Zeile die Prioritätswarteschlange der noch
zu bearbeitenden Knoten, priorisiert nach ihren Wegkosten):

Hinweis: Mit den „Wegkosten“ eines Knotens ist die gegenwärtige
Entfernung dieses Knotens vom Startknoten gemeint.

\begin{bAntwort}
\begin{tabular}{|l|l|l|l|l|l|l|}
\hline
A &
B &
C &
D &
E &
F &
Warteschlange \\\hline\hline

0 & % A
$\infty$ & % B
$\infty$ & % C
$\infty$ & % D
$\infty$ & % E
$\infty$ & % F
A \\\hline % Warteschlange

% A

| & % A
\textbf{4} (A) & % B
\textbf{2} (A) & % C
\textbf{7} (A) & % D
$\infty$ & % E
$\infty$ & % F
C, B, D \\\hline % Warteschlange

% C 2

| & % A
| & % B
| & % C
\textbf{6} (C) & % D
\textbf{7} (C) & % E
$\infty$ & % F
B, D, E \\\hline % Warteschlange

% B 4

| & % A
| & % B
| & % C
\textbf{5} (B) & % D
7 (C) & % E
$\infty$ & % F
D, E \\\hline % Warteschlange

% D 5

| & % A
| & % B
| & % C
| & % D
\textbf{6} (D) & % E
9 (D) & % F
E, F \\\hline % Warteschlange

% E 6

| & % A
| & % B
| & % C
| & % D
| & % E
\textbf{8} (E) & % F
F \\\hline % Warteschlange

% F 8

| & % A
| & % B
| & % C
| & % D
| & % E
| & % F
\\\hline % Warteschlange
\end{tabular}
\end{bAntwort}
\end{enumerate}
\end{document}