Kurs:Diskrete Mathematik/9/Klausur mit Lösungen/kontrolle

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	${}\sum$
Punkte	3	3	8	2	1	6	3	5	10	0	1	0	8	8	58

Aufgabe (3 Punkte)

Lösung

1. Der Binomialkoeffizient ist durch

   ${}{\binom {n}{k}}={\frac {n!}{k!(n-k)!}}\,$

   definiert.

2. Ein kommutativer Ring heißt angeordnet, wenn es eine totale Ordnung „${}\geq$“ auf ${}R$ gibt, die die beiden Eigenschaften
   1. Aus ${}a\geq b$ folgt ${}a+c\geq b+c$ für beliebige ${}a,b,c\in R$,
   2. Aus ${}a,b\geq 0$ folgt ${}ab\geq 0$,

   erfüllt.

3. Ordnungstheorie/Geordnete Menge/Kleinstes Element/Definition/Begriff/Inhalt
4. Ungerichteter Graph/Vollständig/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Zusammenhängend/Exzentrizität/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Inzidenzmatrix/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Lösung

1. Es seien ${}M$ und ${}N$ endliche Mengen, die beide ${}n$ Elemente besitzen. Dann gibt es ${}n!$ bijektive Abbildungen von ${}M$ nach ${}N$.
2. Es sei ${}p$ eine Primzahl und ${}p$ teile ein Produkt ${}ab$ von natürlichen Zahlen ${}a,b\in \mathbb {N}$. Dann teilt ${}p$ einen der Faktoren.
3. Es sei ${}M$ eine Menge, es sei ${}I$ eine endliche Indexmenge und zu jedem ${}i\in I$ sei eine Teilmenge ${}M_{i}\subseteq M$ gegeben. Zu einer Teilmenge ${}J\subseteq I$ setzen wir

   ${}M_{J}=\bigcup _{j\in J}M_{j}\,.$

   Für jede Teilmenge ${}J\subseteq I$ gelte

   ${}{\#\left(M_{J}\right)}\geq {\#\left(J\right)}\,.$

   Dann gibt es eine injektive Abbildung

   $f\colon I\longrightarrow M$

   mit

   ${}f(i)\in M_{i}$.

Aufgabe (8 Punkte)

Beweise den Satz über die Addition und endliche Mengen.

Lösung

Die Voraussetzung besagt, dass es eine bijektive Abbildung

$\psi \colon \{1,\ldots ,m\}\longrightarrow M$

und eine bijektive Abbildung

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow N$

gibt. Die Abbildung

${\{1,\ldots ,n\}}\longrightarrow \{m+1,\ldots ,m+n\},\,i\longmapsto m+i,$

ist nach Aufgabe 1.6 (Diskrete Mathematik (Osnabrück 2020)) bijektiv, sei ${}\theta$ die Umkehrabbildung. Somit ist nach Aufgabe 3.28 (Mathematik für Anwender (Osnabrück 2023-2024))  (3)

$\varphi \circ \theta \colon \{m+1,\ldots ,m+n\}\longrightarrow N$

ebenfalls bijektiv. Wir definieren nun eine Abbildung

$F\colon \{1,\ldots ,m+n\}\longrightarrow M\cup N$

durch

${}F(k)={\begin{cases}\psi (k),{\text{ falls }}k\in \{1,\ldots ,m\}\,,\\\varphi (\theta (k)),{\text{ falls }}k\in \{m+1,\ldots ,m+n\}\,.\end{cases}}\,$

Diese Abbildung ist surjektiv, da jedes Element aus ${}M$ durch den ersten Fall und jedes Element aus ${}N$ durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn

${}k\neq \ell \,$

gegeben sind, und das eine Element zu ${}\{1,\ldots ,m\}$ und das andere zu ${}\{m+1,\ldots ,m+n\}$ gehört, so ist ${}F(k)\in M$ und ${}F(\ell )\in N$ (oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von ${}M$ und ${}N$. Wenn hingegen ${}k$ und ${}\ell$ aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von ${}F(k)$ und ${}F(\ell )$ aus der Injektivität von ${}\psi$ bzw. von ${}\varphi \circ \theta$. Insgesamt erhalten wir also eine bijektive Abbildung

$\{1,\ldots ,m+n\}\longrightarrow M\cup N,$

sodass die Anzahl von ${}M\cup N$ gleich ${}m+n$ ist.

Aufgabe (2 (1+1) Punkte)

Für eine Opernaufführung braucht man für die verschiedenen Rollen eine Altstimme, zwei Sopranstimmen, zwei Tenorstimmen und einen Bass. Im Ensemble stehen zwei Altstimmen, drei Sopranistinnen, vier Tenöre und drei Bässe zur Verfügung.

1. Wie viele Besetzungsmöglichkeiten für die Rollen gibt es?
2. Wie viele Möglichkeiten gibt es, die Mitwirkenden auszuwählen, ohne Berücksichtigung der Rolle?

Lösung

1. Für die Altrolle gibt es ${}2$, für die Sopranrollen gibt es ${}3\cdot 2$, für die Tenorrollen gibt es ${}4\cdot 3$ und für die Bassrolle gibt es ${}3$ Möglichkeiten. Insgesamt gibt es also

   ${}2\cdot 6\cdot 12\cdot 3=432\,$

   Besetzungsmöglichkeiten.

2. Wenn man sich fragt, wer überhaupt eingesetzt wird, so muss man aus den jeweiligen Stimmlagen eine passende Anzahl auswählen. Dies führt auf

   ${}{\binom {2}{1}}\cdot {\binom {3}{2}}\cdot {\binom {4}{2}}\cdot {\binom {3}{1}}=2\cdot 3\cdot 6\cdot 3=108\,$

   Möglichkeiten.

Aufgabe (1 Punkt)

Zeige, dass zwischen den Binomialkoeffizienten ${}{\binom {n}{k}}$ und ${}{\binom {n}{k+1}}$ der Zusammenhang

${}{\binom {n}{k+1}}={\binom {n}{k}}\cdot {\frac {n-k}{k+1}}\,$

besteht.

Lösung

Es ist

${}{\begin{aligned}{\binom {n}{k+1}}&={\frac {n\cdot (n-1)\cdot (n-2)\cdots (n-k+2)\cdot (n-k+1)\cdot (n-k)}{(k+1)\cdot k\cdot (k-1)\cdot (k-2)\cdots 2\cdot 1}}\\&={\frac {n\cdot (n-1)\cdot (n-2)\cdots (n-k+2)\cdot (n-k+1)}{k\cdot (k-1)\cdot (k-2)\cdots 2\cdot 1}}\cdot {\frac {n-k}{k+1}}\\&={\binom {n}{k}}\cdot {\frac {n-k}{k+1}}.\end{aligned}}$

Aufgabe (6 (1+1+1+2+1) Punkte)

Wir betrachten die durch die Wertetabelle

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
${}F(x)$	${}3$	${}5$	${}1$	${}7$	${}8$	${}2$	${}6$	${}4$

gegebene Abbildung ${}F$ von

${}M=\{1,2,\ldots ,8\}\,$

in sich selbst.

1. Erstelle eine Wertetabelle für ${}F^{2}=F\circ F$.
2. Erstelle eine Wertetabelle für ${}F^{3}=F\circ F\circ F$.
3. Begründe, dass sämtliche iterierten Hintereinanderschaltungen ${}F^{n}$ bijektiv sind.
4. Bestimme für jedes ${}x\in M$ das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass

   ${}F^{n}(x)=x\,$

   ist.

5. Bestimme das minimale ${}n\in \mathbb {N} _{+}$ mit der Eigenschaft, dass

   ${}F^{n}(x)=x\,$

   für alle ${}x\in M$ ist.

Lösung

1. Es ist

   ${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
   ${}F(F(x))$	${}1$	${}8$	${}3$	${}6$	${}4$	${}5$	${}2$	${}7$

2. Es ist

   ${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$	${}7$	${}8$
   ${}F(F(F(x)))$	${}3$	${}4$	${}1$	${}2$	${}7$	${}8$	${}5$	${}6$

3. Aus der Wertetabelle kann man unmittelbar entnehmen, dass ${}F$ bijektiv ist. Nach [[Abbildung/Hintereinanderschaltung/Bijektiv/Fakt|Kurs:Mathematik für Anwender (Osnabrück 2023-2024)/Abbildung/Hintereinanderschaltung/Bijektiv/Fakt/Faktreferenznummer (Mathematik für Anwender (Osnabrück 2023-2024))]] sind dann sämtliche Hintereinanderschaltungen der Abbildung mit sich selbst wieder bijektiv.
4. Die Abbildungsvorschrift bewirkt

   $1\mapsto 3\mapsto 1$

   und

   $2\mapsto 5\mapsto 8\mapsto 4\mapsto 7\mapsto 6\mapsto 2.$

   Für ${}x=1,3$ ist also ${}n=2$ und für ${}x=2,5,8,4,7,6$ ist ${}n=6$.

5. Bei ${}n=6$ sind nach Teil (4) die Zahlen ${}2,5,8,4,7,6$ wieder an ihrer Stelle, aber auch ${}1,3$ sind an ihrer Stelle, da ${}6$ ein Vielfaches von ${}2$ ist.

Aufgabe (3 Punkte)

Es sei ${}M$ eine Menge mit ${}n$ Elementen. Bestimme die Anzahl der Relationen auf ${}M$, die

1. reflexiv
2. symmetrisch
3. reflexiv und symmetrisch

sind.

Lösung

Es sei ${}M=\{1,\ldots ,n\}$. Eine Relation ${}R$ ist gegeben durch eine bestimmte Menge von geordneten Paaren ${}(x,y)$, ${}x,y\in M$. Daher kann man sich eine Relation auf ${}M$ so vorstellen, dass in einer ${}n\times n$-Tabelle gewisse Stellen angekreuzt werden und andere nicht.

Bei einer beliebigen Relation gibt es keine weiteren Bedingungen, sodass es ${}2^{n^{2}}$ Relationen gibt (das war nicht gefragt).

Bei einer reflexiven Relation muss auf der Diagonalen immer ein Kreuz sein, ansonsten hat man keine Bedingung, es gibt also ${}n^{2}-n=n(n-1)$ freie Stellen und daher ${}2^{n(n-1)}$ reflexive Relationen.

Bei einer symmetrischen Relation hat man oberhalb der Diagonalen (einschließlich dieser) volle Freiheiten (unterhalb der Diagonalen muss sich der Eintrag wiederholen). Da gibt es ${}{\frac {n^{2}-n}{2}}+n={\frac {n^{2}+n}{2}}$ Plätze und somit gibt es ${}2^{\frac {n^{2}+n}{2}}$ symmetrische Relationen.

Bei einer symmetrischen und reflexiven Relation hat man echt oberhalb der Diagonalen volle Wahlfreiheiten. Davon gibt es ${}{\frac {n^{2}-n}{2}}$ Plätze, sodass es ${}2^{\frac {n^{2}-n}{2}}$ symmetrische und reflexive Relationen gibt.

Aufgabe (5 Punkte)

Zeige, dass die Untergruppen von ${}\mathbb {Z}$ genau die Teilmengen der Form

${}\mathbb {Z} d={\left\{kd\mid k\in \mathbb {Z} \right\}}\,$

mit einer eindeutig bestimmten nicht-negativen Zahl ${}d$ sind.

Lösung

Eine Teilmenge der Form ${}\mathbb {Z} d$ ist aufgrund des Distributivgesetzes eine Untergruppe. Es sei umgekehrt ${}H\subseteq \mathbb {Z}$ eine Untergruppe. Bei ${}H=0$ kann man ${}d=0$ nehmen, sodass wir voraussetzen dürfen, dass ${}H$ neben ${}0$ noch mindestens ein weiteres Element ${}x$ enthält. Wenn ${}x$ negativ ist, so muss die Untergruppe ${}H$ auch das Negative davon, also ${}-x$ enthalten, welches positiv ist. D.h. ${}H$ enthält auch positive Zahlen. Es sei nun ${}d$ die kleinste positive Zahl aus ${}H$. Wir behaupten ${}H=\mathbb {Z} d$. Dabei ist die Inklusion ${}\mathbb {Z} d\subseteq H$ klar, da mit ${}d$ alle (positiven und negativen) Vielfachen von ${}d$ dazugehören müssen. Für die umgekehrte Inklusion sei ${}h\in H$ beliebig. Nach der Division mit Rest gilt

$h=qd+r{\text{ mit }}0\leq r<d.$

Wegen $h\in H$ und $qd\in H$ ist auch ${}r=h-qd\in H$. Nach der Wahl von ${}d$ muss wegen ${}r<d$ gelten: ${}r=0$. Dies bedeutet ${}h=qd$ und damit ${}h\in \mathbb {Z} d$, also ${}H\subseteq \mathbb {Z} d$.

Aufgabe (10 (2+2+5+1) Punkte)

Wir betrachten auf ${}\mathbb {N} _{+}$ die Relation ${}\sim$, die durch

${}m\sim n\,$

festgelegt ist, falls ${}m$ eine Potenz von ${}n$ und ${}n$ eine Potenz von ${}m$ teilt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Bestimme, welche der folgenden Elemente zueinander äquivalent sind, welche nicht.

   $100,\,1000,\,9,\,125,\,500,\,27,\,10,\,210.$

3. Es sei ${}Q$ die Quotientenmenge zu dieser Äquivalenzrelation und es sei ${}\mathbb {P}$ die Menge der Primzahlen mit der Potenzmenge ${}{\mathfrak {P}}\,({\mathbb {P} })$. Zeige, dass es eine natürliche Abbildung

   $\varphi \colon \mathbb {N} _{+}\longrightarrow {\mathfrak {P}}\,({\mathbb {P} })$

   gibt, die zu einer injektiven Abbildung

   ${\tilde {\varphi }}\colon Q\longrightarrow {\mathfrak {P}}\,({\mathbb {P} })$

   führt. Ist ${}{\tilde {\varphi }}$ surjektiv?

4. Wie sieht ein besonders einfaches Repräsentantensystem für die Äquivalenzrelation aus?

Lösung

1. Die Reflexivität ist klar, da ${}n$ die erste Potenz ${}n=n^{1}$ teilt. Die Symmetrie ist von der Formulierung her klar. Zum Nachweis der Transitivität sei ${}\ell \sim m$ und ${}m\sim n$. Dann ist ${}\ell$ ein Teiler von ${}m^{r}$ für ein gewisses ${}r\in \mathbb {N}$ und ${}m$ ist ein Teiler von ${}n^{s}$ für ein gewisses ${}s\in \mathbb {N}$. Dann ist

   ${}\ell a=m^{r}\,$

   und

   ${}mb=n^{s}\,$

   und daraus folgt

   ${}\ell ab^{r}=m^{r}b^{r}=(mb)^{r}={\left(n^{s}\right)}^{r}=n^{sr}\,,$

   sodass ${}\ell$ eine Potenz von ${}n$ teilt. Die umgekehrte Teilbarkeitsbeziehung ergibt sich genauso.

2. Es ist offenbar ${}10\sim 100\sim 1000\sim 500$ (es kommen jeweils die Primfaktoren ${}2$ und ${}5$ vor) und ${}9\sim 27=3^{3}$, darüber hinaus sind ${}125=5^{3}$ und ${}210=2\cdot 3\cdot 5\cdot 7$ nur zu sich selbst äquivalent. Dies ergibt sich aus der Charakterisierung der Relation mit Primteilern aus dem folgenden Teil.
3. Wir betrachten die Abbildung

   $\varphi \colon \mathbb {N} _{+}\longrightarrow {\mathfrak {P}}\,({\mathbb {P} }),\,n\longmapsto \{{\text{Primteiler von }}n\},$

   die einer natürlichen Zahl ${}n\in \mathbb {N} _{+}$ die Menge der in der Primfaktorzerlegung von ${}n$ vorkommenden Primzahlen zuordnet. Es sei ${}m\sim n$. Da in einer Potenz (zu einem positiven Exponenten) die gleichen Primfaktoren vorkommen (nur ihre Vielfachheit ändert sich) folgt aus der Eigenschaft, dass ${}m$ eine Potenz von ${}n$ teilt, dass die Primteiler von ${}m$ in den Primteilern von ${}n$ enthalten sein müssen. Aus ${}m\sim n$ folgt also, dass die Primteiler der beiden Zahlen überhaupt gleich sind. Nach Lemma 11.13 (Diskrete Mathematik (Osnabrück 2020)) gibt es daher eine zugehörige Abbildung

   ${\tilde {\varphi }}\colon Q\longrightarrow {\mathfrak {P}}\,({\mathbb {P} }).$

   Diese ist injektiv, da wenn von ${}m$ und ${}n$ die Primteiler übereinstimmen, dann ${}m$ eine hinreichend große Potenz von ${}n$ teilt und umgekehrt. Diese Abbildung ist nicht surjektiv, da nur endliche Teilmengen der Primzahlen im Bild liegen, es aber unendlich viele Primzahlen gibt.

4. Ein Repräsentantensystem besteht aus allen natürlichen Zahlen mit der Eigenschaft, dass sämtliche Exponenten in ihrer Primfaktorzerlegung gleich ${}1$ sind.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (1 Punkt)

Skizziere ein Pfeildiagramm, das die nebenstehende Permutation überschneidungsfrei darstellt.

Lösung Permutation/Überschneidungsfrei/1/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (8 Punkte)

Beweise den Satz von Kirchhoff über die Anzahl der Spannbäume.

Lösung

Wir führen Induktion über die Anzahl der Knoten. Bei einem einzigen Knoten gibt es einen Spannbaum und die Determinante der leeren Matrix ist ${}1$. Bei zwei Knoten und ${}m$ verbindenden Kanten gibt es ${}m$ Spannbäume. Die Adjazenzmatrix ist ${}{\begin{pmatrix}0&m\\m&0\end{pmatrix}}$ und die Gradmatrix ist ${}{\begin{pmatrix}m&0\\0&m\end{pmatrix}}$. Daher ist die Laplace-Matrix gleich ${}{\begin{pmatrix}m&-m\\-m&m\end{pmatrix}}$. Streicht man die erste Zeile und erste Spalte (oder die zweite Zeile und zweite Spalte). so hat die Streichungsmatrix die Determinante ${}m$. Es sei nun die Aussage für alle Multigraphen mit höchstens ${}n-1$ Knoten bewiesen, und sei eine Multigraph ${}G$ mit ${}n$ Knoten gegeben. Wir führen nun (eine innere) Induktion über die Anzahl ${}m$ der Kanten. Wenn es gar keine Kante gibt, so gibt es keinen Spannbaum und die Laplace-Matrix und die Streichungsmatrix davon ist die Nullmatrix mit Determinante ${}0$. Es sei also die Aussage auch für alle Graphen mit ${}n$ Knoten und mit weniger als ${}m$ Kanten bewiesen, und ${}G$ habe ${}n$ Knoten und ${}m$ Kanten. Wir überlegen uns, was passiert, wenn man eine Kante herausnimmt bzw. kontrahiert. Ohne Einschränkung werden die Kanten zwischen ${}1$ und ${}2$ kontrahiert, wovon es ${}a_{12}\geq 1$ gibt. Die Laplace-Matrix von ${}G$ sei

${\begin{pmatrix}d_{1}&-a_{12}&-a_{13}&\ldots &-a_{1n}\\-a_{12}&d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Laplace-Matrix von ${}G\setminus \{e\}$ ist

${\begin{pmatrix}d_{1}-1&-a_{12}+1&-a_{13}&\ldots &-a_{1n}\\-a_{12}+1&d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{13}&-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\vdots &\ddots &\vdots \\-a_{1n}&-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

und die Laplace-Matrix zur Kontraktion ${}G/e$ ist die ${}(n-1)\times (n-1)$-Matrix

${\begin{pmatrix}d_{1}+d_{2}-2a_{12}&-a_{13}-a_{23}&\ldots &-a_{1n}-a_{2n}\\-a_{13}-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{1n}-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Die Streichungsmatrizen zur jeweils ersten Zeile und ersten Spalte hiervon sind der Reihe nach

${\begin{pmatrix}d_{2}&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}},$

${\begin{pmatrix}d_{2}-1&-a_{23}&\ldots &-a_{2n}\\-a_{23}&d_{3}&\ldots &-a_{3n}\\\vdots &\vdots &\ddots &\vdots \\-a_{2n}&-a_{3n}&\ldots &d_{n}\end{pmatrix}}$

${\begin{pmatrix}d_{3}&\ldots &-a_{3n}\\\vdots &\ddots &\vdots \\-a_{3n}&\ldots &d_{n}\end{pmatrix}}.$

Entwicklung nach der ersten Spalte (für die beiden ersten Matrizen) zeigt, dass die Determinante der ersten Matrix die Summe der Determinanten der beiden folgenden Matrizen ist. Somit folgt die Aussage mit Lemma 18.12 (Diskrete Mathematik (Osnabrück 2020)) aus den beiden Induktionsvoraussetzungen.

Aufgabe weiter

1. Erstelle einen Nachbarschaftsgraphen zu den Bundesländern.
2. Bestimme die Blätter.
3. Was ist der Abstand von Baden-Württemberg zu Niedersachsen?
4. Was ist der Maximalgrad und in welchem Bundesland wird er angenommen?
5. Was ist die Exzentrizität von Thüringen?
6. Ist Deutschland ein Baum?
7. Ist Deutschland hamiltonsch?
8. Ist Deutschland hamiltonsch, wenn man die Blätter herausnimmt?
9. Was ist der Umfang von Deutschland?

Lösung

1. ${}\,$

   

   Achtung, im Bild fehlt Bremen und Berlin!!!

2. Die Blätter sind Bremen, Berlin, Saarland.
3. Der Abstand von Niedersachsen zu Baden-Württemberg ist ${}2$. (über Hessen).
4. Der Maximalgral ist ${}9$, er wird in Niedersachsen angenommen.
5. Die Exzentrizität ist ${}3$ (nach Berlin oder ins Saarland).
6. Deutschland ist kein Baum, da es den Kreis Niedersachsen-Hessen-Thüringen enthält.
7. Deutschland ist nicht hamiltonsch, da es Blätter enthält.
8. Ohne die Blätter ist Deutschland hamiltonsch, ein Hamiltonkreis ist Niedersachsen - Hamburg - SchleswigHolstein - MecklenburgVorpommern - Brandenburg - SachsenAnhalt - Sachsen - Thüringen - Bayern - BadenWürttemberg - Hessen - RheinlandPfalz - NordrheinWestfalen.
9. Der Umfang ist ${}13$. Wegen der drei Blätter kann er nicht größer sein, soeben wurde ein Kreis mit ${}13$ Ländern angegeben.