Kurs:Diskrete Mathematik/9/Klausur/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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (8 Punkte)Referenznummer erstellen

Beweise den Satz über die Addition und endliche Mengen.

Aufgabe * (2 (1+1) Punkte)Referenznummer erstellen

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?

Aufgabe * (1 Punkt)Referenznummer erstellen

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.

Aufgabe * (6 (1+1+1+2+1) Punkte)Referenznummer erstellen

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.

Aufgabe * (3 Punkte)Referenznummer erstellen

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.

Aufgabe * (5 Punkte)Referenznummer erstellen

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.

Aufgabe * (10 (2+2+5+1) Punkte)Referenznummer erstellen

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?

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (1 Punkt)Referenznummer erstellen

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

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (8 Punkte)Referenznummer erstellen

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

Aufgabe * weiterReferenznummer erstellen

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?