\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}