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	7	3	2	0	8	1	0	0	2	55

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, sodass 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 * weiter

Auf der Dating-Plattform „Catch your match“ ist eine Menge ${}M$ von Personen registriert. Es gibt ferner eine Menge ${}E$ von Eigenschaften, über die die Personen verfügen oder nicht (was man dem Profil entnehmen kann). Zu einer Teilmenge an Eigenschaften ${}W\subseteq E$ (Wunscheigenschaften) definieren wir

${}W^{\perp }={\left\{m\in M\mid m{\text{ besitzt alle Eigenschaften aus }}W\right\}}\,$

und zu einer Teilmenge ${}S\subseteq M$ definieren wir

${}S^{\perp }={\left\{e\in E\mid {\text{ jeder Mensch aus }}S{\text{ besitzt die Eigenschaft }}e\right\}}\,.$

1. Beschreibe zu einer Eigenschaft ${}e\in E$ die Menge ${}\{e\}^{\perp }$ mit einem Satz.
2. Beschreibe zu einer Person ${}m\in M$ die Menge ${}\{m\}^{\perp }$ mit einem Satz.
3. Warum ist vermutlich ${}E^{\perp }=\emptyset$?
4. Zeige: Zu Teilmengen ${}W_{1}\subseteq W_{2}$ (in ${}E$) ist

   ${}{\left(W_{1}\right)}^{\perp }\supseteq {\left(W_{2}\right)}^{\perp }\,.$

5. Zeige: Für eine beliebige Teilmenge ${}W\subseteq E$ ist

   ${}W\subseteq {\left(W^{\perp }\right)}^{\perp }\,.$

6. Zeige: Für eine Vereinigung

   ${}W=W_{1}\cup W_{2}\subseteq E\,$

   ist

   ${}{\left(W_{1}\cup W_{2}\right)}^{\perp }={\left(W_{1}\right)}^{\perp }\cap {\left(W_{2}\right)}^{\perp }\,.$

7. Gilt für einen Durchschnitt

   ${}W=W_{1}\cap W_{2}\subseteq E\,.$

   die Beziehung

   ${}{\left(W_{1}\cap W_{2}\right)}^{\perp }={\left(W_{1}\right)}^{\perp }\cup {\left(W_{2}\right)}^{\perp }\,?$

8. Gilt für eine beliebige Teilmenge ${}W\subseteq E$ die Beziehung

   ${}W^{\perp }={\left({\left(W^{\perp }\right)}^{\perp }\right)}^{\perp }\,?$

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?