Kurs:Diskrete Mathematik/5/Klausur mit Lösungen

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.

Lösung

1. Eine Verknüpfung ${}\circ$ auf einer Menge ${}M$ ist eine Abbildung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.$

2. Die natürliche Zahl ${}b$ heißt ein gemeinsames Vielfaches der ${}a_{1},\ldots ,a_{k}$, wenn ${}b$ ein Vielfaches von jedem ${}a_{i}$ ist, also von jedem ${}a_{i}$ geteilt wird.
3. Menge/Partition/Definition/Begriff/Inhalt
4. Ungerichteter Graph/Homomorphismus/Schwach/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Taille/Definition/Begriff/Inhalt
6. Multigraph/Ungerichtet/Definition/Begriff/Inhalt

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.

Lösung

1. Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und ${}N$ eine endliche Menge mit ${}n$ Elementen. Es sei ${}m>n$. Dann gibt es keine injektive Abbildung

   $M\longrightarrow N.$

2. Es seien ${}a,b\in \mathbb {N}$ zwei teilerfremde natürliche Zahlen. Dann gibt es ganze Zahlen ${}r,s\in \mathbb {Z}$ mit ${}ra+sb=1$.
3. Zu einem zusammenhängenden planaren Graphen ist die Anzahl der Gebiete unabhängig von der ebenen Realisierung.

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?

Lösung

1. Eine Möglichkeit ist, zuerst den Rum mit dem Zitronensaft zusammen schütteln, dieses Zwischenprodukt mit den Pfefferminzblättern zusammen rühren und dieses Zwischenprodukt mit dem Orangensaft zusammen schütteln.
2. Für die Verarbeitung gibt es grundsätzlich die beiden skizzierten Verarbeitungsbäume.

   

   

   An den äußeren „Blättern“ gehen die Grundzutaten ein, und an jeder Vereinigungstelle kann geschüttelt oder gerührt werden. Betrachten wir zunächst den linken Verarbeitungsbaum. Da die Situation symmetrisch ist, kann man ohne Einschränkung sagen, dass eine fixierte Zutat (beispielsweise der Orangensaft) im linken Paar verarbeitet wird. Daher gibt es im Wesentlichen drei Möglichkeiten, wie die Zutaten paarweise aufgeteilt werden. Für jede Zutatenaufteilung kann man sich in jedem Verarbeitungsschritt entscheiden, ob man schüttelt oder rührt. Somit gibt es ${}3\cdot 8=24$ Möglichkeiten im linken Verarbeitungsbaum.

   Betrachten wir nun den rechten Verarbeitungsbaum. Es gibt ${}{\binom {4}{2}}=6$ zweielementige Teilmengen und somit sechs Auswahlmöglichkeiten für das zuerst zu verarbeitende Zutatenpaar. Für die mit dem daraus resultierenden Zwischenprodukt zu verarbeitende Zutat gibt es jeweils zwei Möglichkeiten, also gibt es ${}12$ Möglichkeiten für die Zutatenreihenfolge. Unter Berücksichtigung der Verarbeitungstechniken gibt es hier somit ${}12\cdot 8=96$. Insgsamt gibt es also ${}24+96=120$ mögliche Cocktails.

Aufgabe (2 Punkte)

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

Lösung

Bei einer Verknüpfung wird jedem Paar ${}(x,y)\in M\times M$ ein Element aus ${}M$ zugeordnet. Dabei hat man für jedes der ${}k^{2}$ Paare ${}k$ Möglichkeiten. Damit gibt es insgesamt ${}k^{(k^{2})}$ Verknüpfungen.

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)\,?$

Lösung

1. Wenn ${}A\in {\mathfrak {P}}\,(T)$ ist, so bedeutet dies ${}A\subseteq T$, was wegen ${}T\subseteq M$ direkt ${}A\subseteq M$ und somit ${}A\in {\mathfrak {P}}\,(M)$ ergibt.
2. Die Menge ${}\{a\}$ gehört nicht zu ${}{\mathfrak {P}}\,(T)$, da ${}a\notin T$ ist. Die Menge ${}\{a\}$ gehört zu ${}{\mathfrak {P}}\,(M)$ und wegen

   ${}M\setminus T=\{a,d\}\,$

   gehört sie auch zu ${}{\mathfrak {P}}\,(M\setminus T)$.

3. Die Zugehörigkeit von ${}A$ zu ${}{\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)$ bedeutet, dass in ${}A$ nicht nur gerade Zahlen vorkommen, und die Zugehörigkeit von ${}A$ zu ${}{\mathfrak {P}}\,(M\setminus T)$ bedeutet, dass in ${}A$ nur ungerade Zahlen vorkommen.
4. Wir betrachten ${}T$ und ${}M$ aus Teil (3). Die Menge ${}A=\{1,2\}$ gehört zu ${}{\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)$, aber nicht zu ${}{\mathfrak {P}}\,(M\setminus T)$.
5. Das gilt nicht. Die leere Menge gehört zu jeder Potenzmenge, daher gehört sie zu ${}{\mathfrak {P}}\,(M\setminus T)$, aber nicht zu ${}{\mathfrak {P}}\,(M)\setminus {\mathfrak {P}}\,(T)$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

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

Lösung

Es ist

${}\prod _{j=1}^{n}(k+j)={\frac {(k+n)!}{k!}}=n!{\frac {(k+n)!}{n!k!}}=n!{\binom {k+n}{k}}\,.$

Da der Binomialkoeffizient ${}{\binom {k+n}{k}}$ eine ganze Zahl ist, folgt, dass das Produkt der ${}n$ aufeinanderfolgenden Zahlen von ${}n!$ geteilt wird.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

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

Lösung

Zum Nachweis der Assoziativität seien ${}x,y,z$ gegeben. Wir vergleichen ${}(x\sqcup y)\sqcup z$ und ${}x\sqcup (y\sqcup z)$. Es ist

${}x,y\leq x\sqcup y\leq (x\sqcup y)\sqcup z\,$

und ebenso

${}z\leq (x\sqcup y)\sqcup z\,.$

Damit ist also

${}x,y,z\leq (x\sqcup y)\sqcup z\,.$

Da ${}y\sqcup z$ das Supremum von ${}y$ und ${}z$ ist, folgt

${}y\sqcup z\leq (x\sqcup y)\sqcup z\,.$

Daher ist auch

${}x\sqcup (y\sqcup z)\leq (x\sqcup y)\sqcup z\,.$

Die andere Abschätzung gilt genauso, aus der Antisymmetrie der Ordnung folgt somit die Gleichheit.

Aufgabe (7 Punkte)

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

Lösung

Bei ${}n=0$ ist der Restklassenring gleich ${}\mathbb {Z}$ selbst und kein Körper. Bei ${}n=1$ besteht der Restklassenring aus nur einem Element und es ist ${}{\overline {0}}\,={\overline {1}}\,$. Dies ist bei einem Körper explizit ausgeschlossen, und ${}1$ ist keine Primzahl. Es sei also von nun an ${}n\geq 2$. Wenn ${}n$ keine Primzahl ist, so gibt es eine Darstellung

${}n=rs\,$

mit kleineren Zahlen

${}1<r,s<n\,.$

Im Restklassenring ${}\mathbb {Z} /(n)$ bedeutet dies, dass die Restklassen ${}{\overline {r}}\,$ und ${}{\overline {s}}\,$ nicht ${}0$ sind, dass aber ihr Produkt

${}{\overline {r}}\,{\overline {s}}\,={\overline {rs}}\,={\overline {n}}\,=0\,$

ist. Das kann nach Lemma 5.14 (Diskrete Mathematik (Osnabrück 2020)) in einem Körper nicht sein.

Sei nun ${}n$ eine Primzahl. Wir müssen zeigen, dass jede von ${}0$ verschiedene Restklasse ${}{\overline {r}}\,$, ${}0<r<n$, ein inverses Element besitzt. Da ${}n$ prim ist, sind ${}r$ und ${}n$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${}a,b$ mit

${}ar+bn=1\,.$

Dies führt im Restklassenring zur Identität

${}{\begin{aligned}{\overline {1}}\,&={\overline {ar+bn}}\,\\&={\overline {a}}\,{\overline {r}}\,+{\overline {b}}\,{\overline {n}}\,\\&={\overline {a}}\,{\overline {r}}\,,\end{aligned}}$

die besagt, dass ${}{\overline {r}}\,$ und ${}{\overline {a}}\,$ invers zueinander sind.

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 }\,?$

Lösung

1. Das ist die Menge aller Personen, die diese Eigenschaft erfüllen.
2. Das ist die Menge aller Eigenschaften, die diese Person besitzt.
3. Es gibt vermutlich in ${}E$ Eigenschaften, die sich ausschließen, wie klein und groß (oder Katzenfreund/Kein Katzenfreund).
4. Es sei ${}m\in {\left(W_{2}\right)}^{\perp }$. Dies bedeutet, dass ${}m$ eine Person ist, die alle Eigenschaften aus ${}W_{2}$ erfüllt. Dann erfüllt ${}m$ erst recht alle Eigenscahften aus der Teilmenge ${}W_{1}$, also gilt ${}m\in {\left(W_{1}\right)}^{\perp }$.
5. Es sei ${}e\in W$. Die Menge ${}W^{\perp }$ besteht aus allen Personen, die alle Eigenschaften aus ${}W$ besitzen. Diese Personenmenge besitzt insbesondere die Eigenschaft ${}e$, daher ist ${}e\in {\left(W^{\perp }\right)}^{\perp }$.
6. Wegen ${}W_{1}\subseteq W_{1}\cup W_{2}$ gilt nach Teil (4)

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

   und entsprechend für ${}W_{2}$. Dies ergibt die Inklusion ${}{\left(W_{1}\cup W_{2}\right)}^{\perp }\subseteq W_{1}^{\perp }\cap W_{1}^{\perp }$. Es sei nun ${}m=W_{1}^{\perp }\cap W_{1}^{\perp }$. Dies bedeutet, dass ${}m$ alle Eigenschaften aus ${}W_{1}$ und alle Eigenschaften aus ${}W_{2}$ besitzt. Also besitzt ${}m$ alle Eigenschaften aus ${}W_{1}\cup W_{2}$, also ${}m\in {\left(W_{1}\cup W_{2}\right)}^{\perp }$.

7. Dies muss nicht gelten. Es kann beispielsweise ${}E$ disjunkt zerlegt in ${}W_{1}$ und ${}W_{2}$ sein. Dann ist ${}W_{1}\cap W_{2}=\emptyset$ und ${}\emptyset ^{\perp }=M$. Es kann aber gleichzeitig sein, dass es sowohl in ${}W_{1}$ als auch in ${}W_{2}$ widersprüchliche Eigenschaften, sodass

   ${}{\left(W_{1}\right)}^{\perp }=\emptyset ={\left(W_{2}\right)}^{\perp }\,$

   gilt.

8. Das gilt. Nach (4) ist ${}W\subseteq {\left(W^{\perp }\right)}^{\perp }$, woraus mit (5) die Inklusion

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

   Die zu (4) analoge Eingenschaft gilt auch für Teilmengen ${}T\subseteq M$. Angewendet auf ${}T=W^{\perp }$, ergibt sich

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

Aufgabe (3 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Stiergraphen.

Lösung

Die beiden Blätter müssen entweder auf sich selbst oder auf das jeweils andere abgebildet werden. Die an den Blättern anliegenden Knoten werden immer zusammen mit den Blättern getauscht (oder eben nicht getauscht), da sonst die Eigenschaft eines Graphhomomorphismuses verletzt wird, dass adjazente Knoten auf adjazente Knoten abgebildet werden. Der unterste Knoten muss immer auf sich selbst abgebildet werden, da er mit den darüber liegenden Knoten verbunden bleiben muss. Der Typ der Automorphismengruppe ist also ${}\mathbb {Z} /(2)$.

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?

Lösung

Dies ist nicht möglich. Von jedem Eckpunkt aus gelangt man mit einem Pferdsprung nur in eines der inneren vier Felder. Nehmen wir an, es gibt eine solche Durchlaufungskette. Es können maximal zwei Ecken am Anfang oder am Ende dieser Durchlaufungskette stehen. Es gibt also mindestens zwei Ecken, die sowohl einen Vorgänger als auch einen Nachfolger haben. Wenn diese benachbart sind, so sind dadurch schon alle inneren Felder abgedeckt und für die beiden anderen Ecken gibt es keine Anschlussmöglichkeit. Wenn sie gegenüber liegen, so liegt ein Viererzyklus vor, und eben keine vollständige Kette.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (8 Punkte)

Beweise den Satz von Berge.

Lösung

Nehmen wir zuerst an, dass es einen alternierenden Weg gibt, der die Punkte ${}u$ und ${}v$ verbindet, die beide nicht durch die Paarung abgedeckt sind. Wir müssen zeigen, dass man eine Paarung konstruieren kann, die mehr Kanten als die gegebene Paarung besitzt. Es sei

$\{u,u_{2}\},\{u_{2},u_{3}\},\ldots ,\{u_{n-1},v\}$

der alternierende Weg. Dabei gehören die beiden Endkanten nicht zu ${}P$, da die beiden Endpunkte nicht durch ${}P$ abgedeckt sind. Die Länge des Weges, also ${}n-1$, ist ungerade. Wir modifizieren nun die Paarung, indem wir die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ gerade herausnehmen und die Kanten ${}\{u_{i},u_{i+1}\}$ für ${}i$ ungerade hinzunehmen. Dabei wird die Gesamtzahl der Kanten um ${}1$ erhöht. Ferner handelt es sich nach wie vor um eine Paarung. Würde es nämlich in der neuen Paarung einen Knotenpunkt geben, der mit zwei Kanten inzident ist, so würde eine Kante davon gleich ${}\{u_{i},u_{i+1}\}$ sein (mit ${}i$ ungerade) und die andere Kante gleich ${}\{u_{i},x\}$ (oder gleich ${}\{u_{i+1},x\}$) Wenn diese zweite Kante nicht zum alternierenden Weg gehört, so gehört sie zu ${}P$ und würde zusammen mit ${}\{u_{i-1},u_{i}\}$ (bzw. $\{u_{i+1},u_{i+2}\}$) der Paarungseigenschaft von ${}P$ widersprechen. Wenn sie zum alternierenden Weg gehört, so wäre sie gleich ${}\{u_{j},u_{j+1}\}$ mit ${}j$ ungerade, und dann würden die an dem Durchschnittspunkt anliegenden Kanten aus ${}P$ der Paarungseigenschaft von ${}P$ widersprechen (bei den Endkanten muss man etwas anders argumentieren).

Nehmen wir nun an, dass ${}P$ nicht optimal ist. Es sei ${}Q$ eine optimale Paarung, die ja dann nach Definition mehr Kanten als ${}P$ besitzt. Es ist zu zeigen, dass es einen alternierenden Weg für ${}P$ gibt, dessen Endpunkte von ${}P$ nicht abgedeckt sind. Wir betrachten den Graphen ${}H$ auf ${}V$ mit der symmetrischen Differenz von ${}P$ und ${}Q$ als Kantenmenge. Da ${}Q$ mehr Kanten als ${}P$ besitzt, gibt es in ${}H$ mehr Kanten aus ${}Q\setminus P$ als aus ${}P\setminus Q$. Dies muss dann auch für eine Zusammenhangskomponente von ${}H$ gelten, und deren Möglichkeiten sind in Lemma 21.1 (Diskrete Mathematik (Osnabrück 2020)) aufgelistet. Daher muss eine Komponente ein linearer Graph sein, mit Kanten abwechselnd aus ${}P$ und ${}Q$ und wobei die Endkanten aus ${}Q\setminus P$ sind. Die Endpunkte sind dann insbesondere verschieden und nicht durch ${}P$ abgedeckt.

Aufgabe (1 Punkt)

Zeige, dass der abgebildete Graph hamiltonsch ist.

Lösung Bidiakiswürfel/Hamiltonsch/Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

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

Lösung Schachfigur/3x3/König/Planarer Graph/Aufgabe/Lösung