Kurs:Diskrete Mathematik/9/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Der Binomialkoeffizient ${}{\binom {n}{k}}$.
2. Ein angeordneter kommutativer Ring ${}R$.
3. Ein kleinstes Element in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Ein vollständiger Graph.
5. Die Exzentrizität eines Punktes  ${}v\in V$  eines zusammenhängenden Graphen  ${}G=(V,E)$. 
6. Die Inzidenzmatrix zu einem Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von bijektiven Abbildungen.
2. Das Lemma von Euklid.
3. Der Paarungssatz (Heiratssatz)

Aufgabe (2 Punkte)

In einer Schulklasse gibt es ${}32$ Kinder; es wurden vier identische Pizzen bestellt, die gerecht auf die Kinder verteilt werden sollen. Es steht ein beliebig langes Messer zur Verfügung. Zeige, dass man durch ${}10$ Schnitte die Aufteilung erreichen kann (die Pizzen dürfen nicht übereinander gelegt werden, und die Pizzen dürfen im gesamten Schneidevorgang nicht bewegt werden).

Aufgabe * (8 Punkte)

Beweise den Satz über die Addition und endliche Mengen.

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?

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.

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.

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.

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.

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?

Aufgabe (0 Punkte)

Aufgabe (1 Punkt)

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

Aufgabe (0 Punkte)

Aufgabe * (8 Punkte)

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

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?