Kurs:Diskrete Mathematik/5/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	2	5	0	3	0	4	7	0	3	2	0	8	1	0	0	2	48

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Verknüpfung ${}\circ$ auf einer Menge ${}M$.
2. Ein gemeinsames Vielfaches zu natürlichen Zahlen ${}a_{1},\ldots ,a_{k}$.
3. Eine Partition einer Menge ${}M$.
4. Ein schwacher Homomorphismus zwischen Graphen.
5. Die Taille eines Graphen.
6. Ein (ungerichteter, schleifenfreier) Multigraph.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Das Schubfachprinzip (oder Taubenschlagprinzip).
2. Das Lemma von Bezout für teilerfremde natürliche Zahlen ${}a$ und ${}b$.
3. Der Satz über die Gebietsanzahl bei planaren Graphen.

Aufgabe * (5 (1+4) Punkte)

Ein Cocktailmixer verfügt über zwei Verarbeitungstechniken, nämlich schütteln und rühren, wobei in jedem Arbeitsgang stets zwei Grundzutaten bzw. Zwischenprodukte miteinander verarbeitet werden. Bei jedem Cocktail wird jede Grundzutat bei genau einem Arbeitsvorgang verarbeitet (wobei die dabei entstehenden Zwischenprodukte weiterverarbeitet werden können). Als Grundzutaten stehen Orangensaft, Zitronensaft, Pfefferminzblätter und Rum zur Verfügung.

1. Beschreibe die Zubereitung eines Cocktails, so dass jede Verarbeitungstechnik mindestens einmal vorkommt.
2. Auf wie viele Arten kann er aus den Zutaten einen Cocktail mixen?

Aufgabe * (2 Punkte)

Es sei ${}M$ eine ${}k$-elementige Menge. Wie viele Verknüpfungen gibt es auf ${}M$?

Aufgabe * (5 (1+1+1+1+1) Punkte)

Es sei ${}T\subseteq M$ eine Teilmenge einer Menge ${}M$ mit dem Komplement ${}M\setminus T$.

1. Zeige

   ${}{\mathfrak {P}}\,(T)\subseteq {\mathfrak {P}}\,(M)\,.$

2. Es sei ${}M=\{a,b,c,d,e\}$ und ${}T=\{b,c,e\}$. Zu welchen Potenzmengen gehört die Menge ${}\{a\}$? Zu ${}{\mathfrak {P}}\,(T)$? Zu ${}{\mathfrak {P}}\,(M)$? Zu ${}{\mathfrak {P}}\,(M\setminus T)$?
3. Es sei ${}M=\mathbb {N}$ und ${}T$ die Teilmenge der geraden Zahlen. Formuliere in Worten, was die Zugehörigkeit einer Teilmenge ${}A\subseteq \mathbb {N}$ zu ${}{\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)$ und zu ${}{\mathfrak {P}}\,(M\setminus T)$ bedeutet.
4. Gilt

   ${}{\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)\subseteq {\mathfrak {P}}\,(M\setminus T)\,?$

5. Gilt

   ${}{\mathfrak {P}}\,(M\setminus T)\subseteq {\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)\,?$

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

Es sei ${}n\in \mathbb {N} _{+}$. Zeige, dass das Produkt von ${}n$ aufeinanderfolgenden natürlichen Zahlen von ${}n!$ geteilt wird.

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Zeige, dass in einem (ordnungstheoretischen) Verband die Verknüpfung ${}\sqcup$ assoziativ ist.

Aufgabe * (7 Punkte)

Beweise den Satz über die Körpereigenschaft der Restklassenringe ${}\mathbb {Z} /(n)$.

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Stiergraphen.

Aufgabe * (2 Punkte)

Wir betrachten die Züge des Springers im Schach auf einem ${}4\times 4$-Brett. Ist es möglich, durch eine Zugfolge mit dem Springer alle Felder genau einmal zu treffen?

Aufgabe (0 Punkte)

Aufgabe * (8 Punkte)

Beweise den Satz von Berge.

Aufgabe (1 Punkt)

Zeige, dass der abgebildete Graph hamiltonsch ist.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (2 Punkte)

Ist der Spielzuggraph zur Schachfigur König auf einem ${}3\times 3$-Feld planar?