\documentclass{uebungsblatt}
\usepackage{tkz-graph}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{14}
\gruppe{11}

\SetUpEdge[lw=1.5pt,
           color=black,
	   labelcolor=white,
	   labelstyle={sloped,above}]
\tikzset{node distance = 3cm}
\tikzset{VertexStyle/.append  style={minimum height=3.0em}}

\begin{document}

\aufgabe

\teilaufgabe

Mit dem Algorithmus von Kruskal ist es sehr einfach aus dem Graphen von
Tutoraufgabe 2 des Übungsblattes 13 einen minimalen Spannbaum zu erstellen.
Dabei nimmt man zuerst den ursprünglichen Graphen her (hier in schwarz
gezeichnet), also einen gewichteten, zusammenhängenden Graphen. Dann wählt man
die Kante mit dem kleinsten Gewicht aus und markiert sie als ``dem Spannbaum
angehörig'' (hier in grün dargestellt). Dies wäre die Kante zwischen Karlsruhe
und Mannheim, mit dem Wert 68. Danach sucht man nach der nächstkleinere Kante.
Diese muss nicht zu den bereits gefundenen Spannbaum verbunden sein, sie darf
jedoch nicht dazu führen, dass der Spannbaum einen Kreis aufweist -- in diesem
Fall nimmt man solange die nächstgrößere Kante bis entweder alle Kanten
versucht worden sind (dann ist man fertig) oder eine passende Kante hinzugefügt
wird. Im Fall dass zwei Kanten das selbe Gewicht haben und genausogut in den
Spannbaum passen würden, nimmt man zufällig erst die eine, dann die andere auf,
so wie im vorliegenden Graphen die Kante zwischen Kassel und Dortmund und
zwischen Nürnberg und München.

Der fertige Graph sieht nun folgendermaßen aus:

\begin{tikzpicture}
  % define the vertices + orientations
  \Vertex{M}
  \WE(M){UL}
  \NO(M){N}
  \NOWE(N){KS}
  \WE(UL){S}
  \WE(S){KA}
  \NO(KA){MA}
  \NO(MA){F}
  \NOWE(F){K}
  \NOEA(K){DO}

  % normal, black nodes
  \Edge[label=$294$](UL)(F)
  \Edge[label=$228$](N)(F)
  \Edge[label=$189$](F)(K)
  \Edge[label=$465$](UL)(KS)
  % green nodes, part of the spanning tree
  \tikzstyle{EdgeStyle} = [color=green]
  \Edge[label=$138$](M)(UL)
  \Edge[label=$165$](M)(N)
  \Edge[label=$92$](UL)(S)
  \Edge[label=$82$](S)(KA)
  \Edge[label=$68$](KA)(MA)
  \Edge[label=$88$](MA)(F)
  \Edge[label=$83$](K)(DO)
  \Edge[label=$182$](N)(KS)
  \Edge[label=$165$](KS)(DO)
\end{tikzpicture}

\teilaufgabe

\begin{enumerate}
  \item

F = \{Ulm, Stuttgart, Karlsruhe, Mannheim, Frankfurt, Nürnberg, Kassel, 
Dortmund, Köln\}.

d[Ulm] = 138, d[Stuttgart] = $\infty$, d[Karlsruhe] = $\infty$, 
d[Mannheim] = $\infty$, d[Frankfurt] = $\infty$, d[Nürnberg] = 165,
d[Kassel] = $\infty$, d[Dortmund] = $\infty$, d[Köln] = $\infty$,
d[München] = 0.

p[Ulm] = München, p[Nürnberg] = München

  \item

u = Ulm

F = \{Stuttgart, Karlsruhe, Mannheim, Frankfurt, Nürnberg, Kassel, Dortmund,
Köln\}.

Updates:

d[Kassel] = 603, d[Stuttgart] = 230, d[Frankfurt] = 432

p[Kassel] = Ulm, p[Stuttgart] = Ulm, p[Frankfurt] = Ulm

  \item

u = Nürnberg

F = \{Stuttgart, Karlsruhe, Mannheim, Frankfurt, Kassel, Dortmund, Köln\}.

Updates:

d[Kassel] = 347, d[Frankfurt] = 393

p[Kassel] = Nürnberg, p[Frankfurt] = Nürnberg

  \item

u = Stuttgart

F = \{Karlsruhe, Mannheim, Frankfurt, Kassel, Dortmund, Köln\}.

Updates:

d[Karlsruhe] = 312

p[Karlsruhe] = Stuttgart

  \item

u = Karlsruhe

F = \{Mannheim, Frankfurt, Kassel, Dortmund, Köln\}.

Updates:

d[Mannheim] = 380

p[Mannheim] = Karlsruhe

  \item

u = Kassel

F = \{Mannheim, Frankfurt, Dortmund, Köln\}.

Updates:

d[Dortmund] = 512

p[Dortmund] = Karsruhe

  \item

u = Mannheim

F = \{Frankfurt, Dortmund, Köln\}.

Updates: keine neuen kürzeren Wege.

  \item

u = Frankfurt

F = \{Dortmund, Köln\}.

Updates: keine neuen kürzeren Wege.

  \item

u = Dortmund

F = \{Köln\}.

Updates:

d[Köln] = 595

d[Köln] = Dortmund

  \item

u = Köln

F = $\emptyset$

Updates: keine neuen kürzeren Wege.
\end{enumerate}

Rücktraversierung von Köln aus mithilfe von $p$ liefert (Köln, Dortmund,
Kassel, Nürnberg, München) mit 595~km.

\aufgabe

\teilaufgabe

\begin{enumerate}
  \item $19 - (\lfloor 19 \div 3 \rfloor \cdot 3) = 1 \Rightarrow x = 1$
  \item Wenn man $3^n~mod~5$ mit kleinen Zahlen berechnet kommt man zum
    Schluss, dass die Ergebnisse zyklisch sind, in der Reihenfolge
    (1, 3, 4, 2). Somit muss man nur herausfinden, auf welches Element
    des Zyklus der Exponent 30 fällt. Dazu kann man trivial, wie in
    obiger Aufgabe $30~mod~4$ berechnen, dessen Ergebnis 2 ist. Somit
    fällt das Ergebnis auf die 3. Stelle des Zyklus (da der Zyklus
    mit 0 anfängt). Dies bedeutet also, dass $3^{30}~mod~5 = 4$.
    Eine Probe in Maple, \texttt{3**30 mod 5;} bestätigt dieses Ergebnis.
  \item $-20 - (\lfloor -20 \div 7 \rfloor \cdot 7) = -20 - (-21) = 1$
\end{enumerate}

\teilaufgabe

Man kann sich zur Hilfe nehmen, dass $(a + b)~mod~m = [(a~mod~m) +
(b~mod~m)]~mod~m$ gilt. Somit kann man erst jeden einzelnen Summanden Modulo 6
rechnen und dann erst das gesamte Ergebnis Modulo 6.

$10^n~mod~6$ hat einen sehr kurzen Zyklus, nämlich (4), somit ist auch
$10^{17}~mod~6 = 4$. Bei $5^n~mod~6$ ist der Zyklus (1, 5); der Index
entspricht dem Exponenten modulo Zykluslänge, $23~mod~2 = 1$. Somit ist der
Wert von $5^{23}~mod~6 = 5$. Bei $30^n~mod~6$ ist der Zyklus noch einfacher, er
enthält nur (0), somit ist es klar, dass das Ergebnis von $30^100~mod~6 = 0$
ist und dieser Summand gar nicht in die Berechnung eingeht. Nun rechnet man mit
den simplen Zahlen weiter: $(4 + 5)~mod~6 = 3$, somit ist das Ergebnis 3.

Wenn man das Ergebnis nachprüfen will, kann man sich von Maple helfen lassen:
\texttt{(10 \&\^\ 17 + 5 \&\^\ 23 - 30 \&\^\ 100) mod 6;}

\teilaufgabe

Analog zu der zweiten Aufgabe bei 2.1 kann man auch hier einen Zyklus
bei $2^n~mod~14$ beobachten, nämlich (2, 4, 8). Wenn man nun
$7346790100~mod~14$ rechnet bekommt man als Ergebnis 1, was man auf
den Index 0, also den Wert 2 des Zyklus übersetzen kann. Somit
ist das Ergebnis des Terms 2. Eine Prüfung mit Maple,
\texttt{2 \&\^\ 7346790100 mod 14;} bestätigt das Ergebnis.

\aufgabe

Eine Komposition ist immer assoziativ, somit ist diese Eigenschaft gegeben,
zum Beweis der anderen Eigenschaften einer Gruppe kann man die folgende
Tabelle mit der Komposition der einzelnen Funktionen betrachten:

% expand the table a bit more
\setlength{\tabcolsep}{0.6cm}
\renewcommand{\arraystretch}{2}

\begin{tabular}{c||c|c|c|c|c|c}
$\circ$ & $x$ & $\frac{1}{x}$ & $1 - x$ & $\frac{1}{1 - x}$ & $\frac{x}{x - 1}$ & $\frac{x - 1}{x}$ \\
\hline
\hline
$x$ & $x$ & $\frac{1}{x}$ & $1 - x$ & $\frac{1}{1-x}$ & $\frac{x}{x-1}$ & $\frac{x-1}{x}$ \\
\hline
$\frac{1}{x}$ & $\frac{1}{x}$ & $x$ & $\frac{x-1}{x}$ & $\frac{x}{x-1}$ & $1-x$ & $1-x$ \\
\hline
$1-x$ & $1-x$ & $\frac{1}{1-x}$ & $x$ & $\frac{1}{x}$ & $\frac{x-1}{x}$ & $\frac{x}{x-1}$ \\
\hline
$\frac{1}{1-x}$ & $\frac{1}{1-x}$ & $1-x$ & $\frac{x}{x-1}$ & $\frac{x-1}{x}$ & $x$ & $x$ \\
\hline
$\frac{x}{x-1}$ & $\frac{x}{x-1}$ & $\frac{x-1}{x}$ & $\frac{1}{1-x}$ & $1-x$ & $x$ & $\frac{1}{x}$ \\
\hline
$\frac{x-1}{x}$ & $\frac{x-1}{x}$ & $\frac{x}{x-1}$ & $\frac{1}{x}$ & $1-x$ & $x$ & $1-x$
\end{tabular}

Es fällt auf, dass $x$ sowohl das links- als auch das rechtsinverse Element
ist. Zusätzlich kommt in jeder Zeile das neutrale Element $x$ mindestens
ein Mal vor, was bedeutet dass es für jede Komposition von $f$ ein $g$
gibt, dass dessen inverses Element ist. Was ebenfalls auffällt ist, dass
die Tabelle abgeschlossen ist, d.h das Ergebnis jeder Komposition ist auch
wieder Teil der Trägermenge.

Damit wäre die Trägermenge und die Komposition assoziativ $\checkmark$,
abgeschlossen $\checkmark$, hätte ein neutrales Element $\checkmark$ und
jedes Element hätte ein inverses $\checkmark$. Somit ist die Trägermenge
bezüglich der Komposition eine Gruppe. $\qed$

\aufgabe

\teilaufgabe

\teilaufgabe

Die Ordnung bedeutet, dass ein Element $ord(x)$ mal verknüpft werden
muss, um das neutrale Element zu ergeben.

\begin{flalign*}
(a \circ b)^4 & = e \\
(a \circ b)^2 (b \circ a)^2 & = e \\
(a^2 \circ ab \circ ab \circ b^2) (a^2 \circ ab \circ ab \circ b^2) & = e \\
(a \circ b \circ a \circ b) (a \circ b \circ a \circ b) & = e \\
(a^2 \circ b^2) (a^2 \circ b^2) & = e \\
e & = e
\end{flalign*}

\teilaufgabe

Ein Beispiel wäre $\langle \Z, +\rangle$, wo etwa das Element 1 eine
unendliche Ordnung hat.

\aufgabe

\teilaufgabe

Die Untergruppen sind $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14\}$
(gesamte Gruppe, gilt auch als Untergruppe), $\{0, 3, 6, 9, 12\}$, $\{0, 5,
10\}$ und $\{0\}$ die mit der Mächtigkeit 15, 5, 3 und 1 (also Teiler der
Mächtigkeit der Gruppe) alle möglichen Untergruppen abdecken.

Alle betrachteten Untergruppen sind zyklisch, da $\langle \Z_{15}, +_{15}
\rangle$ eine endliche, zyklische Gruppe ist und jede Untergruppe einer
zyklischen Gruppe auch wieder zyklisch ist.

\teilaufgabe

Die Untergruppen kann man über die Gleichung $S = \{ n \cdot z | n \in \N, z
\in Z\}$ aufstellen -- d.h. man nimmt alle Zahlen aus $\Z$ und multipliziert
sie mit einem Faktor $n$ so dass Untergruppen wie $\{1, 2, 3, 4, ...\}$ (bei
$n = 1$) oder $\{2, 4, 6, 8, ...\}$ (bei $n = 2$) entstehen.

Alle so konstruierten Untergruppen sind zyklisch, da $\langle \Z, + \rangle$
eine unendliche, zyklische Gruppe ist und jede Untergruppe einer zyklischen
Gruppe auch wieder zyklisch ist.

\end{document}