\documentclass{uebungsblatt}
\usepackage{tikz}
\usepackage{subfig}
\author{Marek Kubica, kubica@in.tum.de}
\fach{Diskrete Strukturen}
\blatt{12}
\gruppe{11}

\begin{document}

\aufgabe

Der Beweis läuft sehr ähnlich zu dem der Stirlingzahlen zweiter Art ab.
Durch die Einschränkung des Wertes von $k$ auf $n-2$ gibt es zwei 
Möglichkeiten für die mögliche Länge und Anzahl von Zyklen:

\begin{enumerate}
  \item Es gibt einen 3-Zyklus. Man wählt also aus den $n$ Zahlen 3 aus,
    ${n \choose 3}$. Diese Zahlen kann man auf $(3 - 1)! = 2$ verschiedene
    Arten anordnen (eine simple Permutation, $3!$ ist nicht möglich, da
    es identische Zyklen generieren würde). Somit sind für diese Möglichkeit
    ${n \choose 3} \cdot 2$ Möglichkeiten anzusetzen.
  \item Es gibt zwei 2-Zyklen. Für diese Zyklen kann man ${n \choose k-2}$
    Zahlen auswählen, die dann noch auf 3 verschiedene Arten angeordnet
    werden können. Da $k = n - 2$ gilt ist für diese Möglichkeit 
    ${n \choose n-4} \cdot 3$ Möglichkeiten.
\end{enumerate}

Damit ist die Gesamtformel ${n \choose 3} \cdot 2 + {n \choose n-4} \cdot 3$.

\begin{flalign*}
s_{n,n-2} & = {n \choose 3} \cdot 2 + {n \choose n-4} \cdot 3 & \\
 & = \frac{n!}{3! \cdot (3-n)!} \cdot 2 + \frac{n!}{(n-4)! \cdot (n-n+4)!} \cdot 3 & \text{Binomialkoeffizienten aufgelöst} \\
 & = \frac{n! \cdot 2}{6 \cdot (3-n)!} + \frac{n! \cdot 3}{(n-4)! \cdot 24} & \text{Fakultäten aufgelöst} \\
 & = \frac{n!}{3 \cdot (3-n)!} + \frac{n!}{(n-4)! \cdot 8} & \text{Zahlen gekürzt} \\
 & = \frac{n(n-1)(n-2)}{3} + \frac{n(n-1)(n-2)(n-3)}{8} & \text{Fakultäten gekürzt} \\
 & = \frac{8n(n-1)(n-2) + 3n(n-1)(n-2)(n-3)}{24} & \text{Hauptnenner gebildet, zusammengefasst} \\
 & = \frac{1}{24} \cdot \left[8n(n-1)(n-2) + 3n(n-1)(n-2)(n-3)\right] & \\
 & = \frac{1}{24} \cdot \left\{[n(n-1)(n-2)][8+3(n-3)]\right\} & \text{Ausgeklammert} \\
 & = \frac{1}{24} \cdot \left\{[n(n-1)(n-2)][3n-1]\right\} & \text{Überflüssige Klammern entfert} \\
 & = \frac{1}{24} \cdot n(n-1)(n-2)(3n-1) & \qed \\
\end{flalign*}

\aufgabe

\teilaufgabe

$ p = p_1 \circ p_2 \circ p_3 \circ p_4 = p_1(p_2(p_3(p_4))) $

Also wird zuerst $p_4$ angewendet, danach $p_3$ usw. und das Ergebnis
ist $p$. In der folgenden Matrix stellt jede Zeile die Anwendung der
nächsten Permutation dar:

\begin{math}
  \begin{pmatrix}
  1 & 2 & 3 & 4 & 5 \\
  1 & 2 & 4 & 5 & 3 \\
  1 & 3 & 4 & 2 & 5 \\
  2 & 3 & 4 & 5 & 1 \\
  2 & 3 & 1 & 4 & 5
  \end{pmatrix}
\end{math}

Somit ist das Ergebnis:

\begin{math}
  \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    2 & 3 & 1 & 4 & 5
  \end{pmatrix}
\end{math}

Oder auch in Zyklenschreibweise $p =$ (1 2 3).

\teilaufgabe

\begin{math}
  p_1 \circ p_4 = p_1(p_4) = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    1 & 2 & 4 & 5 & 3 \\
    5 & 2 & 1 & 4 & 3
  \end{pmatrix} = \begin{pmatrix}
    1 & 2 & 3 & 4 & 5 \\
    5 & 2 & 1 & 4 & 3
  \end{pmatrix} = \text{(1 5 3)}
\end{math}

Der längste Zyklus ist 3, alle anderen Zyklen in der Permutation haben die
Länge 1 (nicht aufgeführt). Somit muss $k = 3$ sein, damit die Permutation
wieder zur ursprünglichen Reihenfolge zurückkehrt.

\aufgabe

\teilaufgabe

Die Gradfolge $1, 2, 3, 4, 4, 4, 4$ besagt, dass es mindestens einen Graphen
gibt, bei dem fünf Knoten miteinander verbunden sind und maximal zwei Knoten
die eine oder mehrere Komponenten bilden.  Wenn man die Kanten in zwei
Komponenten gruppieren wollte, könnte man ${4, 4, 4, 4, 3}, {2, 1}$
herausbekommen. Damit wären die Knoten mit den höchsten Graden in einer
Komponente (unabhängig davon ob das nun von der Anzahl der Kanten überhaupt
aufgeben würde, aber das ist für diese Betrachtung nicht von Belang). Somit
bliebe noch die Komponente ${2, 1}$, die aber, da ein Knoten Grad zwei hat so
nicht existieren kann, da sie mindestens noch eine Kante zur anderen Komponente
braucht und somit der Graph zusammenhängend wäre.  Andere Möglichkeiten für die
zweielementige Komponente sind ebenfalls nicht möglich, da die Komponente nur
existieren kann wenn sie aus Knoten von Grad ${1, 1}$ bestehen würde, es aber
nur einen Knoten vom Grad 1 gibt -- jede andere Knotenkombination in der
Komponente müsste \emph{mindestens} eine Kante zur größeren, 5-Elementigen
Komponente besitzen. Andere Möglichkeiten wie ein dreikomponentiger Graph sind
nicht möglich, da zwei Komponenten vom Grad 0 nötig wären, diese aber nicht in
der Gradfolge vorkommen.

Insgesamt hat der Graph laut dem Handshaking-Theorem $ \frac{\sum deg(v)}{2} =
11$ Kanten.

\teilaufgabe

Zwischen den Knoten des einen Graphen $G$, und denen des anderen $G^{\prime}$
besteht eine Bijektion $\{a \rightarrow i, b \rightarrow j, c \rightarrow k,
d \rightarrow l, e \rightarrow m, f \rightarrow n, g \rightarrow o \}$. Es
ist jedoch möglich die Kanten in dem Graphen $G^{\prime}$ so zu ändern,
dass $V$ und $V^{\prime}$ unterschiedliche Mengen enthalten. Der
Graph in \figurename~\ref{graphs-b} ist eine Version des Graphen in
\figurename~\ref{graphs-a} in dem die Kanten $\{a, b\}$ und $\{c, b\}$
durch die Kanten $\{k, j\}$ und $\{l, j\}$ ersetzt wurden. Diese Kanten
sind nicht in der Bijektion $G \rightarrow G^{\prime}$ somit sind
die Graphen nicht isomorph.

\figurename~\ref{graphs} zeigt beide Graphen.

\begin{figure}[!ht]%
  \centering
  \subfloat[Ein einfacher Graph]{
\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: four -- six
  \draw [] (116bp,218bp) .. controls (124bp,207bp) and (133bp,193bp)  .. (139bp,180bp) .. controls (148bp,156bp) and (151bp,127bp)  .. (152bp,108bp);
  % Edge: one -- two
  \draw [] (103bp,432bp) .. controls (103bp,421bp) and (103bp,407bp)  .. (103bp,396bp);
  % Edge: three -- seven
  \draw [] (90bp,290bp) .. controls (82bp,280bp) and (72bp,266bp)  .. (67bp,252bp) .. controls (36bp,177bp) and (39bp,151bp)  .. (52bp,72bp) .. controls (54bp,60bp) and (58bp,46bp)  .. (62bp,36bp);
  % Edge: two -- three
  \draw [] (103bp,360bp) .. controls (103bp,349bp) and (103bp,335bp)  .. (103bp,324bp);
  % Edge: five -- seven
  \draw [] (99bp,144bp) .. controls (93bp,116bp) and (80bp,64bp)  .. (73bp,36bp);
  % Edge: six -- seven
  \draw [] (136bp,76bp) .. controls (122bp,63bp) and (100bp,45bp)  .. (86bp,32bp);
  % Edge: four -- seven
  \draw [] (89bp,219bp) .. controls (81bp,208bp) and (71bp,194bp)  .. (67bp,180bp) .. controls (52bp,130bp) and (60bp,66bp)  .. (65bp,36bp);
  % Edge: three -- four
  \draw [] (103bp,288bp) .. controls (103bp,277bp) and (103bp,263bp)  .. (103bp,252bp);
  % Edge: five -- six
  \draw [] (114bp,146bp) .. controls (122bp,134bp) and (133bp,118bp)  .. (141bp,107bp);
  % Edge: four -- five
  \draw [] (103bp,216bp) .. controls (103bp,205bp) and (103bp,191bp)  .. (103bp,180bp);
  % Edge: three -- six
  \draw [] (116bp,290bp) .. controls (123bp,279bp) and (133bp,265bp)  .. (139bp,252bp) .. controls (159bp,203bp) and (157bp,139bp)  .. (155bp,108bp);
  % Node: seven
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (69bp,18bp) ellipse (27bp and 18bp);
  \draw (69bp,18bp) node {g};
\end{scope}
  % Node: six
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (153bp,90bp) ellipse (27bp and 18bp);
  \draw (153bp,90bp) node {f};
\end{scope}
  % Node: three
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (103bp,306bp) ellipse (27bp and 18bp);
  \draw (103bp,306bp) node {c};
\end{scope}
  % Node: two
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (103bp,378bp) ellipse (27bp and 18bp);
  \draw (103bp,378bp) node {b};
\end{scope}
  % Node: four
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (103bp,234bp) ellipse (27bp and 18bp);
  \draw (103bp,234bp) node {d};
\end{scope}
  % Node: five
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (103bp,162bp) ellipse (27bp and 18bp);
  \draw (103bp,162bp) node {e};
\end{scope}
  % Node: one
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (103bp,450bp) ellipse (27bp and 18bp);
  \draw (103bp,450bp) node {a};
\end{scope}
\end{tikzpicture}
  \label{graphs-a}}
  \subfloat[Graph mit geänderten Kanten]{
\begin{tikzpicture}[>=latex,join=bevel,]
  \pgfsetlinewidth{1bp}
%%
\pgfsetcolor{black}
  % Edge: four -- six
  \draw [] (124bp,218bp) .. controls (116bp,207bp) and (107bp,193bp)  .. (101bp,180bp) .. controls (91bp,156bp) and (86bp,127bp)  .. (84bp,108bp);
  % Edge: one -- three
  \draw [] (27bp,216bp) .. controls (27bp,205bp) and (27bp,191bp)  .. (27bp,180bp);
  % Edge: three -- seven
  \draw [] (28bp,144bp) .. controls (29bp,125bp) and (33bp,94bp)  .. (46bp,72bp) .. controls (56bp,54bp) and (75bp,40bp)  .. (89bp,30bp);
  % Edge: two -- three
  \draw [] (101bp,289bp) .. controls (92bp,270bp) and (77bp,240bp)  .. (63bp,216bp) .. controls (56bp,203bp) and (46bp,189bp)  .. (39bp,179bp);
  % Edge: five -- seven
  \draw [] (134bp,144bp) .. controls (128bp,116bp) and (118bp,64bp)  .. (113bp,36bp);
  % Edge: six -- seven
  \draw [] (89bp,72bp) .. controls (93bp,61bp) and (98bp,47bp)  .. (103bp,36bp);
  % Edge: four -- seven
  \draw [] (151bp,218bp) .. controls (159bp,208bp) and (168bp,194bp)  .. (173bp,180bp) .. controls (177bp,164bp) and (176bp,159bp)  .. (173bp,144bp) .. controls (163bp,101bp) and (136bp,57bp)  .. (121bp,34bp);
  % Edge: two -- four
  \draw [] (116bp,289bp) .. controls (120bp,277bp) and (126bp,263bp)  .. (130bp,251bp);
  % Edge: five -- six
  \draw [] (125bp,146bp) .. controls (116bp,134bp) and (103bp,118bp)  .. (94bp,106bp);
  % Edge: four -- five
  \draw [] (137bp,216bp) .. controls (137bp,205bp) and (137bp,191bp)  .. (137bp,180bp);
  % Edge: three -- six
  \draw [] (39bp,146bp) .. controls (48bp,134bp) and (61bp,118bp)  .. (70bp,106bp);
  % Node: seven
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (109bp,18bp) ellipse (27bp and 18bp);
  \draw (109bp,18bp) node {o};
\end{scope}
  % Node: six
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (82bp,90bp) ellipse (27bp and 18bp);
  \draw (82bp,90bp) node {n};
\end{scope}
  % Node: three
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,162bp) ellipse (27bp and 18bp);
  \draw (27bp,162bp) node {k};
\end{scope}
  % Node: two
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (109bp,306bp) ellipse (27bp and 18bp);
  \draw (109bp,306bp) node {j};
\end{scope}
  % Node: four
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (137bp,234bp) ellipse (27bp and 18bp);
  \draw (137bp,234bp) node {l};
\end{scope}
  % Node: five
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (137bp,162bp) ellipse (27bp and 18bp);
  \draw (137bp,162bp) node {m};
\end{scope}
  % Node: one
\begin{scope}
  \pgfsetstrokecolor{black}
  \draw (27bp,234bp) ellipse (27bp and 18bp);
  \draw (27bp,234bp) node {i};
\end{scope}
\end{tikzpicture}
  \label{graphs-b}}
  \caption{Zwei nicht isomorphe Graphen mit gleicher Gradfolge}
  \label{graphs}
\end{figure}

\teilaufgabe

Es gibt keinen bipartiten Graphen mit 7 Knoten, da die Partitionen eines
Graphen jeweils 3 und 4 Knoten enthalten müssten. Hier gäbe es wiederrum
zwei Möglichkeiten: 

\begin{enumerate}
  \item alle Knoten vom Grad vier in einer Partition, 
    $\{\{1, 2, 3\}, \{4, 4, 4, 4\}\}$. Dies würde aber bedeuten, dass
    ein Knoten vom Grad vier zu vier Knoten aus der anderen Partition
    verbunden wird. Ist aber unmöglich, da die andere Partition nur
    drei Elemente enthält.
  \item alle Knoten vom Grad vier sind in der dreielementigen Partition,
    $\{\{4, 4, 4\}, \{1, 2, 3, 4\}$. Somit muss die vierelementige
    Partition also mindestens einen Knoten vom Grad vier enthalten und dies
    würde bedingen dass die jeweils andere Partition mindestens vier
    Elemente enthält was nicht möglich ist.
\end{enumerate}

Somit ist es nicht möglich, zwei Partitionen des Graphen mit dieser
Reihenfolge zu konstruieren und damit kann ein Graph mit dieser Gradfolge
nicht bipartit sein.

\aufgabe

Man geht zuerst von dem Stern aus, d.h der Stern hat $k+1$ Knoten und $k$
Kanten die gleich dem Grad des Mittelpunktes sind. Die Knoten drumherum haben
alle Grad 1. Der Gesamtgrad hat $n$ Knoten, also müssen an den Kreis
noch $n - (k+1)$ Knoten hinzugefügt werden. 

Als Beispiel ein Stern von Grad 5, an den zwei Knoten angehängt werden sollen: 
Um eine Knoten an einen Stern mit 6 Knoten anzuhängen gibt es $2^6$ 
Möglichkeiten, da der neue Knoten mit null oder bis zu 6 weiteren Knoten
verbunden ist. An diesen resultierenden Graphen soll nun ein weiterer Knoten
angehängt werden, es gibt also $2^7$ Möglichkeiten. Für diesen Kreis gibt
es also $2^6 \cdot 2^7 = 2^{6+7} = 2^{13} = 8192$ Möglichkeiten. 

Allgemein bedeutet dies, dass der Exponent die Summe von $k+1$ bis $n-1$ ist.
Diese Summe ist gleich der Differenz der Summe von 1 bis $n-1$ und 1 bis $k$
(als Beispiel für diese Überlegung kann man die Summe aller Zahlen von 3 bis 5
wählen: $(1 + 2 + 3 + 4 + 5) - (1 + 2) = (3 + 4 + 5)$). Dadurch kann man nun
die Gaußsche Summenformel anwenden, $\frac{(n-1)n}{2} - \frac{k(k+1)}{2} =
\frac{n(n-1) - k(k+1)}{2}$. Die Anzahl der Möglichkeiten ist somit
$2^{\frac{n(n-1) - k(k+1)}{2}}$.

Nun sind das die Möglichkeiten für einen bestimmten Kreis, es sind aber mehrere
Kreise möglich, bei einem Teilgraph mit $k+1$ Knoten sind das $k+1$
verschiedene Möglichkeiten den Mittelpunkt des Sternes zu setzen. Somit
muss auch dieser Term noch dazumultipliziert werden (multipliziert, da es
je nach Mittelpunkt $2^{\cdots}$ verschiedene Möglichkeiten gibt, Knoten
anzufügen. Das Ergebnis ist somit:

\begin{flalign*}
2^{\frac{n(n-1) - k(k+1)}{2}} \cdot (k+1)
\end{flalign*}

\end{document}
