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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Ring ${}R$.
2. Relation/Rechtseindeutig/Definition/Begriff
3. Ein Gruppenhomomorphismus zwischen Gruppen ${}(G,\circ ,e_{G})$ und ${}(H,\circ ,e_{H})$.
4. Ungerichteter Graph/Untergraph/Voll/Definition/Begriff
5. Ungerichteter Graph/Weg/Länge/Definition/Begriff
6. Ungerichteter Graph/Gradmatrix/Definition/Begriff

Lösung

1. Eine Menge ${}R$ heißt ein Ring, wenn es zwei Verknüpfungen (genannt Addition und Multiplikation)

   $+:R\times R\longrightarrow R{\text{ und }}\cdot :R\times R\longrightarrow R$

   und (nicht notwendigerweise verschiedene) Elemente ${}0,1\in R$ gibt, die die folgenden Eigenschaften erfüllen.

   1. Axiome der Addition
      1. Assoziativgesetz: Für alle ${}a,b,c\in R$ gilt: ${}(a+b)+c=a+(b+c)$.
      2. Kommutativgesetz: Für alle ${}a,b\in R$ gilt ${}a+b=b+a$.
      3. ${}0$ ist das neutrale Element der Addition, d.h. für alle ${}a\in R$ ist ${}a+0=a$.
      4. Existenz des Negativen: Zu jedem ${}a\in R$ gibt es ein Element ${}b\in R$ mit ${}a+b=0$.
   2. Axiome der Multiplikation
      1. Assoziativgesetz: Für alle ${}a,b,c\in R$ gilt: ${}(a\cdot b)\cdot c=a\cdot (b\cdot c)$.
      2. ${}1$ ist das neutrale Element der Multiplikation, d.h. für alle ${}a\in R$ ist ${}a\cdot 1=1\cdot a=a$.
   3. Distributivgesetz: Für alle ${}a,b,c\in R$ gilt ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)$ und ${}(b+c)\cdot a=(b\cdot a)+(c\cdot a)$.
2. Relation/Rechtseindeutig/Definition/Begriff/Inhalt
3. Eine Abbildung

   $\psi \colon G\longrightarrow H$

   heißt Gruppenhomomorphismus, wenn die Gleichheit

   ${}\psi (g\circ g')=\psi (g)\circ \psi (g')\,$

   für alle ${}g,g'\in G$ gilt.

4. Ungerichteter Graph/Untergraph/Voll/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Weg/Länge/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Gradmatrix/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Division mit Rest für die ganzen Zahlen.
2. Der Multinomialsatz für einen kommutativen Halbring.
3. Die eulersche Polyederformel.

Lösung

1. Es sei ${}d$ eine fixierte positive natürliche Zahl. Dann gibt es zu jeder ganzen Zahl ${}n$ eine eindeutig bestimmte ganze Zahl ${}q$ und eine eindeutig bestimmte natürliche Zahl ${}r$, ${}0\leq r\leq d-1$, mit

   ${}n=qd+r\,.$

2. Es sei ${}R$ ein kommutativer Halbring und seien ${}x_{1},\ldots ,x_{k}\in R$ Elemente und ${}n\in \mathbb {N}$. Dann ist

   ${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

3. Es sei ${}G$ ein zusammenhängender planarer Graph mit ${}n$ Knotenpunkten, ${}m$ Kanten und ${}g$ Gebieten. Dann gilt die eulersche Polyederformel

   ${}n-m+g=2\,.$

Aufgabe (3 Punkte)

Bestimme die Anzahl der Tripel ${}(i,j,k)\in \mathbb {N} ^{3}$ mit

${}i+j+k=5\,.$

Lösung

Wenn ${}i$ fixiert ist, so muss

${}j+k=5-i\,$

sein. D.h. ${}j$ läuft zwischen ${}0$ und ${}5-i$ und legt dabei ${}k$ eindeutig fest. Somit gibt es bei fixiertem ${}i$ genau ${}6-i$ Möglichkeiten. Da ${}i=0,1,\ldots ,5$ ist, gibt es insgesamt also

$6+5+4+3+2+1=21$

erlaubte Tripel.

Aufgabe (4 Punkte)

Es seien ${}M$ und ${}N$ Mengen und seien ${}A\subseteq M$ und ${}B\subseteq N$ Teilmengen. Zeige die Gleichheit

${}{\left(A\times N\right)}\cap {\left(M\times B\right)}=A\times B\,.$

Lösung

Wir zeigen die beiden Inklusionen. Es sei zunächst

${}(x,y)\in {\left(A\times N\right)}\cap {\left(M\times B\right)}\,.$

Dies bedeutet

${}(x,y)\in {\left(A\times N\right)}\,$

und

${}(x,y)\in {\left(M\times B\right)}\,.$

Dies bedeutet einerseits ${}x\in A$ und andererseits ${}y\in B$. Also ist ${}(x,y)\in A\times B$.

Wenn umgekehrt ${}(x,y)\in A\times B$ gilt, so ist ${}x\in A$ und ${}y\in B$. Wegen der Teilmengenbeziehungen ${}A\subseteq M$ und ${}B\subseteq N$ ist

${}(x,y)\in {\left(A\times N\right)}\,$

und

${}(x,y)\in {\left(M\times B\right)}\,$

und damit auch

${}(x,y)\in {\left(A\times N\right)}\cap {\left(M\times B\right)}\,.$

Aufgabe (7 Punkte)

Beweise den Satz über die Anzahl von fixpunktfreien Permutationen.

Lösung

Zu jedem ${}i\in {\{1,\ldots ,n\}}$ sei ${}A_{i}$ die Menge aller Permutationen auf ${}{\{1,\ldots ,n\}}$, die ${}i$ auf sich selbst abbilden. Somit ist ${}A_{1}\cup A_{2}\cup \ldots \cup A_{n}$ die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu ${}J\subseteq {\{1,\ldots ,n\}}$ die Durchschnitte ${}\bigcap _{i\in J}A_{j}$ verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus ${}J$ Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von ${}J$ haben können). Wenn die Anzahl von ${}J$ gleich ${}k$ ist, so gibt es ${}(n-k)!$ solche Permutationen, da ja die Permutation auf ${}J$ die Identität sein muss und es außerhalb von ${}J$ keine Einschränkung gibt. Bei fixiertem ${}k$ wissen wir auch, wie viele Teilmengen ${}J$ mit ${}k$ Elementen zu berücksichtigen sind, nämlich ${}{\binom {n}{k}}$. Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck

${}{\begin{aligned}{\#\left(A_{1}\cup A_{2}\cup \ldots \cup A_{n}\right)}&=\sum _{k=1}^{n}(-1)^{k+1}{\binom {n}{k}}(n-k)!\\&=\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!(n-k)!}}(n-k)!\\&=\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!}}.\end{aligned}}$

Somit ist die Anzahl der fixpunktfreien Permutationen gleich

${}n!-\sum _{k=1}^{n}(-1)^{k+1}{\frac {n!}{k!}}=n!+\sum _{k=1}^{n}(-1)^{k}{\frac {n!}{k!}}=\sum _{k=0}^{n}(-1)^{k}{\frac {n!}{k!}}\,.$

Aufgabe (6 (1+1+1+1+2) Punkte)

Wir definieren die Folge (der sogenannten Bernoulli-Zahlen) ${}B_{n}$, ${}n\in \mathbb {N}$, durch ${}B_{0}=1$ und für ${}n\geq 1$ durch die rekursive Bedingung

${}\sum _{j=0}^{n}{\binom {n+1}{j}}B_{j}=0\,.$

1. Berechne ${}B_{1}$.
2. Berechne ${}B_{2}$.
3. Berechne ${}B_{3}$.
4. Berechne ${}B_{4}$.
5. Zeige, dass alle ${}B_{n}$ rationale Zahlen sind.

Lösung

1. Für ${}n=1$ ist die rekursive Bedingung gleich

   ${}{\begin{aligned}0&=\sum _{j=0}^{1}{\binom {2}{j}}B_{j}\\&=B_{0}+2B_{1}\\&=1+2B_{1},\end{aligned}}$

   also ist ${}B_{1}=-{\frac {1}{2}}$.
2. Für ${}n=2$ ist die rekursive Bedingung gleich

   ${}{\begin{aligned}0&=\sum _{j=0}^{2}{\binom {3}{j}}B_{j}\\&=B_{0}+3B_{1}+3B_{2}\\&=1-{\frac {3}{2}}+3B_{2}\\&=-{\frac {1}{2}}+3B_{2},\end{aligned}}$

   also ist ${}B_{2}={\frac {1}{6}}$.
3. Für ${}n=3$ ist die rekursive Bedingung gleich

   ${}{\begin{aligned}0&=\sum _{j=0}^{3}{\binom {4}{j}}B_{j}\\&=B_{0}+4B_{1}+6B_{2}+4B_{3}\\&=1-2+1+4B_{3}\\&=4B_{3},\end{aligned}}$

   also ist ${}B_{3}=0$.
4. Für ${}n=4$ ist die rekursive Bedingung gleich

   ${}{\begin{aligned}0&=\sum _{j=0}^{4}{\binom {5}{j}}B_{j}\\&=B_{0}+5B_{1}+10B_{2}+10B_{3}+5B_{4}\\&=1-{\frac {5}{2}}+{\frac {10}{6}}+5B_{4}\\&={\frac {6-15+10}{6}}+5B_{4}\\&={\frac {1}{6}}+5B_{4},\end{aligned}}$

   also ist ${}B_{4}=-{\frac {1}{30}}$.
5. Wir zeigen die Aussage durch Induktion nach ${}n$, wobei der Induktionsanfang bereits erledigt ist. Zum Beweis des Induktionsschrittes nehmen wir an, das die Rationalität von ${}B_{0},B_{1},\ldots ,B_{n-1}$ bereits bekannt sei. Die Rekursionsbedingung

   ${}\sum _{j=0}^{n}{\binom {n+1}{j}}B_{j}=0\,$

   schreiben wir als

   ${}{\binom {n+1}{n}}B_{n}=-{\left(\sum _{j=0}^{n-1}{\binom {n+1}{j}}B_{j}\right)}\,$

   bzw. als

   ${}B_{n}=-{\frac {\sum _{j=0}^{n-1}{\binom {n+1}{j}}B_{j}}{\binom {n+1}{n}}}\,.$

   Da die Binomialkoeffizienten natürliche Zahlen sind, steht hier wieder eine rationale Zahl.

Aufgabe (1 Punkt)

Bestimme, ob die durch die Gaußklammer gegebene Abbildung

$\mathbb {Q} \longrightarrow \mathbb {Z} ,\,q\longmapsto \lfloor q\rfloor ,$

ein Gruppenhomomorphismus ist oder nicht.

Lösung

Die Gaußklammer definiert keinen Gruppenhomomorphismus, da ${}q=\lfloor {\frac {1}{2}}\rfloor =0$ ist und damit

${}\lfloor {\frac {1}{2}}+{\frac {1}{2}}\rfloor =\lfloor 1\rfloor =1\,,$

aber

${}\lfloor {\frac {1}{2}}\rfloor +\lfloor {\frac {1}{2}}\rfloor =0+0=0\,$

ist.

Aufgabe (3 Punkte)

Es sei ${}R$ ein kommutativer Ring. Zu jedem ${}f\in R$ sei

$\mu _{f}\colon R\longrightarrow R,\,g\longmapsto fg,$

die Multiplikation mit ${}f$. Zeige, dass ${}\mu _{f}$ genau dann bijektiv ist, wenn es surjektiv ist.

Man zeige durch ein Beispiel, dass in dieser Situation aus der Injektivität nicht die Bijektivität folgt.

Lösung

Die Bijektivität impliziert nach Definition stets die Surjektivität. Es sei ${}\varphi _{f}$ surjektiv. Dann gibt es insbesondere ein Urbild der ${}1$, also ein Element ${}g\in R$ mit ${}fg=1$. Dies bedeutet, dass ${}f$ eine Einheit ist. Wegen der Distributivität ist die Abbildung ${}\varphi _{f}$ ein Gruppenhomomorphismus der additiven Gruppe ${}(R,+,0)$. Um die Injektivität zu zeigen wenden wir das Kernkriterium an. Es sei also ${}fh=0$. Dann ist aber

${}0=g(fh)=(fg)h=h\,,$

sodass der Kern nur aus einem

Element besteht.

Es sei ${}R=\mathbb {Z}$. Dann ist die Multiplikation mit ${}f=2$ injektiv, aber nicht surjektiv, da nur gerade Zahlen im Bild liegen.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen und ${}H=(a_{1},\ldots ,a_{k})={\left\{n_{1}a_{1}+n_{2}a_{2}+\cdots +n_{k}a_{k}\mid n_{j}\in \mathbb {Z} \right\}}$ die davon erzeugte Untergruppe. Zeige, dass eine ganze Zahl ${}t$ genau dann ein gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$ ist, wenn ${}H\subseteq \mathbb {Z} t$ ist, und dass ${}t$ genau dann ein größter gemeinsamer Teiler ist, wenn ${}H=\mathbb {Z} t$ ist.

Lösung

Aus ${}H=(a_{1},\ldots ,a_{k})\subseteq (t)$ folgt sofort ${}a_{i}\mathbb {Z} \subseteq t\mathbb {Z}$ für jedes ${}i=1,\ldots ,k$, was gerade bedeutet, dass ${}t$ diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt ${}t$ ein gemeinsamer Teiler. Dann ist ${}a_{i}\in t\mathbb {Z}$ und da ${}H=(a_{1},\ldots ,a_{k})$ die kleinste Untergruppe ist, die alle ${}a_{i}$ enthält, muss ${}H\subseteq t\mathbb {Z}$ gelten.

Aufgrund von Satz 8.4 (Diskrete Mathematik (Osnabrück 2020)) wissen wir, dass es eine ganze Zahl ${}g$ gibt mit ${}H=\mathbb {Z} d$. Für einen anderen gemeinsamen Teiler ${}t$ der ${}a_{i}$ gilt ${}\mathbb {Z} d=H\subseteq \mathbb {Z} t$, sodass ${}d$ von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.

Aufgabe (3 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen und sei

$f\colon M\longrightarrow N$

eine Abbildung. Wie viele Abbildungen

$s\colon N\longrightarrow M$

mit

${}f\circ s=\operatorname {Id} _{N}\,$

gibt es?

Lösung

Die Elemente aus ${}N$ seien mit ${}1,2,\ldots ,n$ bezeichnet. Zu jedem ${}i\in N$ sei

${}M_{i}={\left\{x\in M\mid f(x)=i\right\}}\,$

und

${}m_{i}={\#\left(M_{i}\right)}={\#\left({\left\{x\in M\mid f(x)=i\right\}}\right)}\,$

die Anzahl der Elemente aus ${}M$, die auf ${}i$ abgebildet werden (was ${}0$ sein kann). Da

${}f\circ s=\operatorname {Id} _{N}\,$

gelten soll, muss ${}s(i)\in M_{i}$ für jedes ${}i$ gelten. Somit gibt es

$m_{1}\cdot m_{2}\cdots m_{n}$

Möglichkeiten für solche Abbildungen.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Lösung

Der isolierte Punkt ${}A$ muss unter einem Graphautomorphismus auf sich selbst abgebildet werden. ${}B$ und ${}C$ können offenbar miteinander vertauscht werden. Deshalb gibt es neben der Identität diese Vertauschung und die Automorphismengruppe ist ${}\mathbb {Z} /(2)$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (9 Punkte)

Beweise den Fünf-Farben-Satz.

Lösung

Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens ${}5$ 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 ${}5$ 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 fünf Farben. Wenn die Nachbarn von ${}u$ nur höchstens vier Farben verwenden, was insbesondere dann der Fall ist, wenn ${}u$ höchstens vier Nachbarn besitzt, so kann man unmittelbar eine zulässige Färbung von ${}H$ zu einer zulässigen Färbung von ${}G$ ausbauen, indem man ${}u$ eine Farbe gibt, die in seinen Nachbarn nicht vorkommt.

Der Punkt ${}u$ habe also genau ${}5$ Nachbarn mit ${}5$ verschiedenen Farben. Wir fixieren eine ebene Realisierung und wir bezeichnen die Nachbarn von ${}u$ mit ${}v_{1},v_{2},v_{3},v_{4},v_{5}$ im Uhrzeigersinn (ein kleiner Kreis um ${}u$ in ${}\mathbb {R} ^{2}$, der keinen weiteren Knotenpunkt enthält, trifft jeden Verbindungsweg zu den Nachbarn in einem Punkt der Peripherie, dies legt die Reihenfolge fest). Es sei ${}c$ eine zulässige Färbung auf ${}H$. Wie betrachten den induzierten Untergraphen

${}V_{13}={\left\{v\in H\mid c(v)=c(v_{1}){\text{ oder }}c(v)=c(v_{3})\right\}}\,.$

Wir machen nun eine Fallunterscheidung je nachdem, ob ${}v_{1}$ und ${}v_{3}$ in ${}V_{13}$ miteinander durch einen Weg verbunden sind oder nicht.

Fall 1. Sie sind nicht miteinander verbunden. Es sei ${}W_{13}$ die Zusammenhangskomponente von ${}V_{13}$, die ${}v_{1}$ enthält. Dabei gilt ${}v_{3}\notin W_{13}$. Wir legen jetzt auf ${}H$ eine neue Färbung ${}c'$ fest, indem wir

${}c'(v)={\begin{cases}c(v),\,{\text{ falls }}v\notin W_{13}\,,\\c(v_{3}),\,{\text{ falls }}v\in W_{13}{\text{ und }}c(v)=c(v_{1})\,,\\c(v_{1}),\,{\text{ falls }}v\in W_{13}{\text{ und }}c(v)=c(v_{3})\,.\end{cases}}\,$

festlegen. Für die Knoten aus ${}W_{13}$ werden also die beiden Farben ${}c(v_{1})$ und ${}c(v_{3})$ vertauscht, alle anderen Knoten behalten ihre Farben. Diese Färbung ist wieder zulässig. Dies ist klar für Kanten, die ganz außerhalb von ${}W_{13}$ oder ganz innerhalb von ${}W_{13}$ verlaufen. Bei ${}x\in W_{13}$ und ${}y\notin W_{13}$ besitzt bei ${}y\notin V_{13}$ dieser Knoten eine von ${}c(v_{1})$ und ${}c(v_{3})$ verschiedene Farbe, und bei ${}y\in V_{13}$ gibt es keine Kante.

Fall 2. Es gibt nun einen verbindenen Weg in ${}V_{13}$ von ${}v_{1}$ nach ${}v_{3}$. Wenn es keinen verbindenden Weg von ${}v_{2}$ nach ${}v_{4}$ innerhalb des entsprechend definierten Untergraphen ${}V_{24}$ gibt, so sind wir aufgrund der Argumentation im ersten Fall fertig. Wir sind somit in der Situation, wo es einen Weg ${}P_{13}$ von ${}v_{1}$ nach ${}v_{3}$ in ${}V_{13}$ und einen Weg ${}P_{24}$ von ${}v_{2}$ nach ${}v_{4}$ in ${}V_{24}$ gibt. Wir ergänzen ${}P_{13}$ durch die Kanten ${}\{u,v_{1}\}$ und ${}\{u,v_{3}\}$ zu einem Zykel in ${}G$, der in der ebenen Realisierung einem geschlossenen Weg entspricht (indem wir ${}P_{13}$ ohne Knotenwiederholungen wählen, können wir diesen geschlossenen Weg als überschneidungsfrei annehmen). Hierbei liegt einer der Punkte ${}v_{2}$ oder ${}v_{4}$ im Inneren des durch den Weg begrenzten Gebietes und der andere außerhalb davon. Dann gibt es aber eine Überschneidung der beiden Wege, und diese muss in einem Knotenpunkt vorliegen. Dies ist aber ein Widerspruch, da die Farben ${}c(v_{1}),c(v_{2}),c(v_{3}),c(v_{4})$ alle verschieden sind.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung