Kurs:Diskrete Mathematik/6/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	4	4	5	6	1	0	4	4	0	0	5	1	3	0	0	0	4	47

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Permutation ${}\sigma$ auf einer Menge ${}M$.
2. Eine ordnungstreue Abbildung

   $F\colon M_{1}\longrightarrow M_{2},$

   zwischen den geordneten Mengen ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$.

3. Die Quotientenmenge zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Ein ${}r$-regulärer Graph auf einer Menge ${}V$.
5. Das kartesische Produkt der beiden Graphen ${}G=(V,E)$ und ${}H=(W,F)$.
6. Eine optimale Paarung ${}P\subseteq E$ in einem Graphen ${}G$.

Lösung

1. Eine Permutation ${}\sigma$ auf ${}M$ ist eine bijektive Abbildung

   $\sigma \colon M\longrightarrow M.$

2. Die Abbildung

   $F\colon M_{1}\longrightarrow M_{2},$

   heißt ordnungstreu, wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets auch ${}F(x)\leq _{2}F(x')$ gilt.

3. Man nennt

   ${}M/\sim :={\left\{[x]\mid x\in M\right\}}\,$

   die Quotientenmenge von ${}\sim$.

4. Ein Graph auf ${}V$ heißt ${}r$-regulär, wenn jeder Punkt den Grad ${}r$ besitzt.
5. Das kartesische Produkt besitzt die Knotenmenge ${}V\times W$, und zwischen zwei Knoten ${}(v_{1},w_{1})$ und ${}(v_{2},w_{2})$ liegt genau dann eine Kante, wenn entweder ${}v_{1}=v_{2}$ und ${}\{w_{1},w_{2}\}\in F$ oder ${}w_{1}=w_{2}$ und ${}\{v_{1},v_{2}\}\in E$ gilt.
6. Eine Paarung ${}P\subseteq E$ in ${}G$ heißt optimal, wenn sie unter allen Paarungen von ${}G$ die größtmögliche Anzahl von Kanten enthält.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Beziehung zwischen der Multiplikation und endlichen Mengen.
2. Der Satz über die Untergruppen von ${}\mathbb {Z}$.
3. Der Charakterisierungssatz für bipartite Graphen mittels Kreisen.

Lösung

1. Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen. Dann besitzt die Produktmenge ${}M\times N$ genau ${}m\cdot n$ Elemente.
2. Die Untergruppen von ${}\mathbb {Z}$ sind genau die Teilmengen der Form

   ${}\mathbb {Z} d={\left\{kd\mid k\in \mathbb {Z} \right\}}\,$

   mit einer eindeutig bestimmten nicht-negativen Zahl ${}d$.
3. Ein Graph ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.

Aufgabe (4 Punkte)

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen und sei ${}w$ ein Element, das nicht zu ${}M$ gehöre. Zeige, dass dann die Vereinigung ${}M\cup \{w\}$ genau ${}n'$ Elemente besitzt.

Lösung

Wenn ${}M$ leer ist, so besteht die Vereinigungsmenge ${}M\cup \{w\}$ nur aus dem einzigen Element ${}w$ und steht somit in Bijektion zu ${}\{1\}$. Allgemein liegt eine bijektive Abbildung

$\varphi \colon \{1,\ldots ,n\}\longrightarrow M$

vor. Wir definieren eine Abbildung

$\psi \colon \{1,\ldots ,n,n'\}\longrightarrow M\cup \{w\}$

durch

${}\psi (k):={\begin{cases}\varphi (k),{\text{ falls }}k\in \{1,\ldots ,n\}\\w,{\text{ falls }}k=n'\,.\end{cases}}\,$

Dies ist wohldefiniert. Die Abbildung ist surjektiv, da alle Elemente aus ${}M$ durch Elemente aus ${}\{1,\ldots ,n\}$ getroffen werden und da ${}w$ durch ${}n'$ getroffen wird. Die Abbildung ist auch injektiv. Wenn nämlich ${}j\neq k$ aus der Definitionsmenge sind, so ist, wenn beide zu ${}\{1,\ldots ,n\}$ gehören, direkt

${}\psi (j)=\varphi (j)\neq \varphi (k)=\psi (k)\,.$

Wenn hingegen ${}k=n'$ ist, so ist ${}\psi (j)\in M$ und

${}\psi (n')=w\neq \psi (j)\,.$

Aufgabe (4 (2+2) Punkte)

Gabi Hochster möchte sich die Fingernägel ihrer linken Hand (ohne den Daumennagel) lackieren, wobei die drei Farben ${}B,G,R$ zur Verfügung stehen. Sie möchte nicht, dass zwei benachbarte Finger die gleiche Farbe bekommen.

1. Wie viele Möglichkeiten gibt es, wenn sie nur zwei Farben verwendet?
2. Wie viele Möglichkeiten gibt es, wenn sie alle drei Farben verwendet?

Lösung

1. Wenn nur zwei Farben verwendet werden, sagen wir die Farben ${}X$ und ${}Y$, so legt die Farbe auf dem Zeigefinger alles weitere fest, nämlich ${}XYXY$ oder ${}YXYX$. Da es drei Möglichkeiten gibt, aus drei Farben zwei Farben auszuwählen, gibt es sechs Möglichkeiten, die Nägel mit nur zwei Farben in der beschriebenen Weise zu lackieren.
2. Wenn alle drei Farben vorkommen sollen, so kommt genau eine doppelt und die beiden anderen Farben einfach vor. Für die Wahl der doppelt verwendeten Farbe gibt es drei Möglichkeiten. Für die Auswahl der zwei Finger für diese Farbe gibt es grundsätzlich

   ${}{\binom {4}{2}}=6\,$

   Möglichkeiten, davon sind aber drei Möglichkeiten durch die Nachbarschatsbedingung ausgeschlossen. In jedem dieser Fälle hat man noch zwei Möglichkeiten, wie man die beiden anderen Farben verteilen soll. Also gibt es von diesem Typ

   ${}3\cdot 3\cdot 2=18\,$

   Möglichkeiten.

Aufgabe (5 (1+2+2) Punkte)

Es sei ${}n\in \mathbb {N} _{+}$. Vergleiche die Anzahl der injektiven Abbildungen von einer ${}n$-elementigen Menge in eine ${}n+1$-elementige Menge mit der Anzahl der surjektiven Abbildungen von einer ${}n+1$-elementigen Menge in eine ${}n$-elementige Menge in den folgenden Fällen.

a) ${}n=1$,

b) ${}n=2$,

c) ${}n=3$.

Lösung

a) Es gibt ${}2$ Abbildungen von einer einelementigen Menge in eine zweielementige Menge, die stets injektiv sind. Dagegen gibt es überhaupt nur eine Abbildung von einer zweielementigen Menge auf eine einelementige Menge, die natürlich surjektiv ist.

b) Wir betrachten injektive Abbildungen

$\varphi \colon \{1,2\}\longrightarrow \{1,2,3\}.$

Es gibt ${}3$ Möglichkeiten für ${}\varphi (1)$ und es gibt ${}2$ Möglichkeiten für ${}\varphi (2)$ (da ja ${}\varphi (1)$ schon besetzt ist), also insgesamt ${}6$ Möglichkeiten. Zur Bestimmung der surjektiven Abbildungen

$\varphi \colon \{1,2,3\}\longrightarrow \{1,2\}$

überlegen wir uns, dass dabei ${}2$ Elemente auf ein gleiches Element abgebildet werden müssen. Dafür gibt es ${}3$ Paare. Für das Paar gibt es dann ${}2$ Möglichkeiten, wohin es abgebildet wird, also gibt es ${}6$ surjektive Abbildungen.

c) Wir betrachten injektive Abbildungen

$\varphi \colon \{1,2,3\}\longrightarrow \{1,2,3,4\}.$

Es gibt ${}4$ Möglichkeiten für ${}\varphi (1)$, es gibt ${}3$ Möglichkeiten für ${}\varphi (2)$ (da ja ${}\varphi (1)$ schon besetzt ist) und es gibt ${}2$ Möglichkeiten für ${}\varphi (3)$, also insgesamt ${}24$ Möglichkeiten. Zur Bestimmung der surjektiven Abbildungen

$\varphi \colon \{1,2,3,4\}\longrightarrow \{1,2,3\}$

überlegen wir uns, dass dabei ${}2$ Elemente auf ein gleiches Element abgebildet werden müssen. In einer ${}4$-elementigen Menge gibt es ${}6$ Paare. Wenn das Paar feststeht, so geht es um die Anzahl der bijektiven Abbildungen auf einer ${}3$-elementigen Menge, das sind ${}6$. Also gibt es insgesamt ${}36$ surjektive Abbildungen.

Aufgabe (6 Punkte)

Es sei ${}G$ eine Menge und es seien ${}M_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei

${}M_{J}=\bigcap _{i\in J}M_{i}\,.$

Beweise die Anzahlformel

${}{\#\left(\bigcup _{i=1}^{n}M_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(M_{J}\right)}\right)}\,.$

Lösung

Wir beweisen die Aussage durch Induktion über ${}n$, wobei der Fall ${}n=1$ klar ist. Für ${}n=2$ siehe Aufgabe 1.18 (Diskrete Mathematik (Osnabrück 2020)). Es ist

${}{\begin{aligned}{\#\left(\bigcup _{i=1}^{n+1}A_{i}\right)}&={\#\left({\left(\bigcup _{i=1}^{n}A_{i}\right)}\cup A_{n+1}\right)}\\&={\#\left(\bigcup _{i=1}^{n}A_{i}\right)}+{\#\left(A_{n+1}\right)}-{\#\left({\left(\bigcup _{i=1}^{n}A_{i}\right)}\cap A_{n+1}\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+{\#\left(A_{n+1}\right)}-{\#\left(\bigcup _{i=1}^{n}{\left(A_{i}\cap A_{n+1}\right)}\right)}\\&=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+{\#\left(A_{n+1}\right)}-\sum _{\ell =1}^{n}(-1)^{\ell +1}{\left(\sum _{L\subseteq \{1,\ldots ,n\},\,{\#\left(L\right)}=\ell }{\#\left(A_{L}\cap A_{n+1}\right)}\right)}\\&=\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,n+1\notin J,\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}+\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k,\,n+1\in J}{\#\left(A_{J}\right)}\right)}\\&=\sum _{k=1}^{n+1}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n,n+1\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)},\end{aligned}}$

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung ${}k=\ell +1$ durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

${}J\subseteq \{1,\ldots ,n,n+1\}\,$

je nachdem aufspaltet, ob ${}n+1$ dazu gehört oder nicht.

Aufgabe (1 Punkt)

Es sei ${}G$ eine kommutative Gruppe und

$\varphi \colon G\longrightarrow H$

ein surjektiver Gruppenhomomorphismus. Zeige, dass ${}H$ ebenfalls kommutativ ist.

Lösung

Es seien ${}h_{1},h_{2}\in H$. Dann gibt es ${}g_{1},g_{2}\in G$ mit ${}\varphi (g_{1})=h_{1}$ und ${}\varphi (g_{2})=h_{2}$. Dann ist

${}h_{1}h_{2}=\varphi (g_{1})\varphi (g_{2})=\varphi (g_{1}g_{2})=\varphi (g_{2}g_{1})=\varphi (g_{2})\varphi (g_{1})=h_{2}h_{1}\,.$

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (4 (1+3) Punkte)

Wir betrachten die Menge

${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}\,,$

die mit der stellenweisen Addition ${}+$ von Funktionen eine kommutative Gruppe ist. Auf dieser Menge bildet die Hintereinanderschaltung von Abbildungen ${}\circ$ eine assoziative Verknüpfung mit der Identität als neutralem Element.

1. Zeige, dass das Distributivgesetz in der Form

   ${}(f+g)\circ h=f\circ h+g\circ h\,$

   gilt.

2. Zeige, dass das Distributivgesetz in der Form

   ${}h\circ (f+g)=h\circ f+h\circ g\,$

   nicht gilt.

Lösung

1. Es ist

   ${}{\begin{aligned}((f+g)\circ h)(x)&=(f+g)(h(x))\\&=f(h(x))+g(h(x))\\&=(f\circ h)(x)+(g\circ h)(x)\end{aligned}}$

   für alle ${}x\in \mathbb {R}$, somit ist

   ${}(f+g)\circ h=f\circ h+g\circ h\,$

   für beliebige ${}f,g,h\in \operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$.

2. Es sei ${}h$ die Quadratabbildung, also

   ${}h(x)=x^{2}\,$

   und es sei

   ${}f=g\,$

   die identische Abbildung, also

   ${}f(x)=g(x)=x\,.$

   Dann ist einerseits

   ${}{\begin{aligned}(h\circ (f+g))(1)&=h((f+g)(1))\\&=h(f(1)+g(1))\\&=h(1+1)\\&=h(2)\\&=4\end{aligned}}$

   und andererseits

   ${}{\begin{aligned}(h\circ f+h\circ g)(1)&=(h\circ f)(1)+(h\circ g)(1)\\&=h(f(1))+h(g(1))\\&=h(1)+h(1)\\&=1+1\\&=2.\end{aligned}}$

   Somit ist

   ${}h\circ (f+g)\neq h\circ f+h\circ g\,.$

Aufgabe (4 Punkte)

Zeige, dass beim euklidischen Algorithmus zu ${}a$ und ${}b$ der größte gemeinsame Teiler von zwei aufeinanderfolgenden Resten stets gleich bleibt und schließe daraus, dass der Algorithmus den größten gemeinsamen Teiler der beiden Zahlen berechnet.

Lösung

Die Reste seien mit ${}r_{i}$ bezeichnet. Wenn ${}t$ ein gemeinsamer Teiler von ${}r_{i+1}$ und von ${}r_{i+2}$ ist, so zeigt die Beziehung

${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,,$

dass ${}t$ auch ein Teiler von ${}r_{i}$ und damit ein gemeinsamer Teiler von ${}r_{i+1}$ und von ${}r_{i}$ ist. Die Umkehrung folgt genauso. Daraus folgt mit der Gleichungskette

${}\operatorname {ggT} (a,b)=\operatorname {ggT} (b,r_{2})=\operatorname {ggT} (r_{2},r_{3})=\ldots =\operatorname {ggT} (r_{k-2},r_{k-1})=\operatorname {ggT} (r_{k-1},r_{k})=\operatorname {ggT} (r_{k-1},0)=r_{k-1}\,,$

dass der Algorithmus den größten gemeinsamen Teiler von ${}a$ und ${}b$ berechnet.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (5 (3+2) Punkte)

Es sei ${}G=(V,E)$ ein Graph.

1. Zeige, dass für ${}x,y\in V$ die folgenden Eigenschaften äquivalent sind.
   a) Es ist ${}N(x)\subseteq N(y)$.
   b) Für alle ${}z\in V$ folgt aus ${}xz\in E$ auch ${}yz\in E$.
   c) Die Abbildung

   $\varphi \colon V\longrightarrow V$

   mit

   ${}\varphi (u)={\begin{cases}u\,,{\text{ für }}u\neq x\,,\\y\,,{\text{ für }}u=x\,,\end{cases}}\,$

   ist ein Graphhomomorphismus.

2. Es sei ${}xRy$ die Relation aus (1). Welche Eigenschaften einer Ordnungsrelation erfüllt sie, welche nicht?

Lösung

1. Die Äquivalenz von (1) und (2) ist klar. Es sei (2) erfüllt und sei ${}\varphi$ die angegebene Abbildung. Wenn ${}u,v\neq x$ sind, so werden sie auf sich selbst abgebildet und daher bleiben Kanten erhalten. Sei ${}u\neq x$. Es wird ${}u$ auf sich selbst und ${}x$ auf ${}y$ abgebildet. Wenn es eine Kante zwischen ${}u$ und ${}x$ gibt, dann nach (2) auch zwischen ${}u$ und ${}y$. Es sei umgekehrt (3) erfüllt und sei ${}z\in N(x)$. Dann ist ${}z\neq x$ und ${}xz$ ist eine Kante. Da ein Graphhomomorphismus vorliegt, folgt, dass auch

   ${}\varphi (x)\varphi (z)=yz\,$

   eine Kante ist, also auch ${}z\in N(y)$.

2. Wir argumentieren mit (1). Damit ist unmittelbar klar, dass diese Relation transitiv und reflexiv ist. Sie ist im Allgemeinen aber nicht antisymmetrisch. Betrachten wir den Graphen mit drei Punkten ${}x,y,z$, wobei ${}xz$ und ${}yz$ Kanten seien und ${}xy$ keine Kante. Dann ist

   ${}N(x)=N(y)=\{z\}\,$

   und ${}x$ und ${}y$ stehen in Relation zueinander, sie sind aber nicht gleich.

Aufgabe (1 Punkt)

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge ${}3$ gibt.

Lösung

Aufgabe (3 (1+1+1) Punkte)

1. Ist die abgebildete Paarung maximal?
2. Skizziere eine optimale Paarung für den Graphen.
3. Ist der Graph bipartit?

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (4 Punkte)

Beweise den Sechs-Farben-Satz.

Lösung

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens ${}6$ Knoten unmittelbar klar ist. Es liege also ein ebener Graph ${}G$ mit ${}n$ Knoten vor und für jeden ebenen Graphen mit weniger als ${}n$ Knoten wissen wir, dass es eine zulässige Färbung mit höchstens ${}6$ Farben gibt. Nach Korollar 25.6 (Diskrete Mathematik (Osnabrück 2020))  (2) gibt es einen Knoten ${}u$ mit höchstens ${}5$ Nachbarn. Es sei ${}H$ der Graph, der aus ${}G$ entsteht, wenn man ${}u$ und die an ${}u$ anliegenden Kanten herausnimmt. Nach Induktionsvoraussetzung besitzt ${}H$ eine zulässige Färbung mit höchstens sechs Farben. Die ${}5$ Nachbarn von ${}u$ verwenden höchstens ${}5$ Farben davon und daher kann man für ${}u$ eine sechste Farbe wählen, was insgesamt eine zulässige Färbung von ${}G$ mit ${}6$ Farben ergibt.