Kurs:Diskrete Mathematik/14/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	5	3	4	1	2	4	2	4	2	0	0	0	0	0	8	0	0	41

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine relationstreue Abbildung ${}\varphi \colon M\rightarrow N$, wobei auf ${}M$ und ${}N$ jeweils Relationen fixiert sind.
2. Die (zugehörige) Ordnung in einem algebraischen Verband ${}(M,\sqcap ,\sqcup )$.
3. Die Stirling-Zahl zweiter Art ${}S({n},{k})$.
4. Ein Graphhomomorphismus zwischen den Graphen  ${}G=(V,E)$  und  ${}H=(W,F)$. 
5. Ein Rundgang.
6. Eine minimale Knotenüberdeckung eines Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
2. Die Potenzgesetze für ein Monoid.
3. Der Sechs-Farben-Satz.

Aufgabe * (5 (3+2) Punkte)

Es seien ${}M_{1},\ldots ,M_{k}$ und ${}N_{1},\ldots ,N_{k}$ nichtleere Mengen und

$\varphi _{i}\colon M_{i}\longrightarrow N_{i}$

Abbildungen für ${}i=1,\ldots ,k$. Es sei ${}M=M_{1}\times \cdots \times M_{k}$, ${}N=N_{1}\times \cdots \times N_{k}$, und ${}\varphi$ die Produktabbildung, also

$\varphi \colon M\longrightarrow N,\,(x_{1},\ldots ,x_{k})\longmapsto (\varphi _{1}(x_{1}),\ldots ,\varphi _{k}(x_{k})).$

a) Zeige, dass ${}\varphi$ genau dann surjektiv ist, wenn alle ${}\varphi _{i}$ surjektiv sind.

b) Zeige, dass a) nicht gelten muss, wenn die beteiligten Mengen leer sein dürfen.

Aufgabe * (3 Punkte)

Petra hat folgende Informationen über die Erfolge von Deutschland bei Fußballweltmeisterschaften:

1. Die Fußballweltmeisterschaft findet alle vier Jahre statt.
2. Deutschland war schon viermal Weltmeister.
3. Deutschland war zum ersten Mal 1954 und zum letzten Mal 2014 Weltmeister.
4. Deutschland war nie zweimal hintereinander Weltmeister.

Wie viele Möglichkeiten für die Jahre, in denen Deutschland die zweite bzw. die dritte Weltmeisterschaft gewann, verbleiben?

Aufgabe * (4 Punkte)

Beweise durch Induktion, dass für  ${}n\geq 10$  die Abschätzung

${}3^{n}\geq n^{4}\,$

gilt.

Aufgabe * (1 Punkt)

Es sei ${}M$ eine Menge. Wir betrachten die Verknüpfung

${\mathfrak {P}}\,(M)\times {\mathfrak {P}}\,(M)\longrightarrow {\mathfrak {P}}\,(M),\,(A,B)\longmapsto A\setminus B.$

Ist diese Verknüpfung assoziativ?

Aufgabe * (2 Punkte)

Zeige, dass ein Ring mit  ${}0=1$  der Nullring ist.

Aufgabe * (4 Punkte)

Zeige durch Induktion, dass jede nichtleere Teilmenge  ${}T\subseteq \mathbb {N}$  ein kleinstes Element besitzt.

Aufgabe * (2 Punkte)

Beweise die Formel

${}2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\,$

mit Hilfe des allgemeinen binomischen Lehrsatzes.

Aufgabe * (4 Punkte)

Beweise die Eindeutigkeit der Primfaktorzerlegung für natürliche Zahlen.

Aufgabe * (2 Punkte)

Es seien ${}M$ und ${}N$ Mengen und sei ${}f\colon M\rightarrow N$ eine Abbildung. Zeige, dass durch die Festlegung

${}x\sim y\,,$

wenn

${}f(x)=f(y)\,,$

eine Äquivalenzrelation auf ${}M$ definiert wird.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (8 Punkte)

Beweise den Satz von Ore.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)