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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Fakultät einer natürlichen Zahl ${}n$.
2. Eine linksvollständige Relation ${}R\subseteq M\times N$.
3. Eine obere Schranke zu einer Teilmenge ${}J\subseteq I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Ein starrer Graph.
5. Die Lapace-Matrix zu einem Multigraphen ${}G$.
6. Die chromatische Zahl eines Graphen.

Lösung

1. Unter der Fakultät von ${}n$ versteht man die Zahl

   ${}n!:=n(n-1)(n-2)\cdots 3\cdot 2\cdot 1\,.$

2. Die Relation ${}R\subseteq M\times N$ heißt linksvollständig, wenn es zu jedem ${}x\in M$ ein ${}y\in N$ mit ${}(x,y)\in R$ gibt.
3. Ein Element ${}x\in I$ heißt obere Schranke für ${}J$, wenn ${}y\preccurlyeq x$ für jedes ${}y\in J$ gilt.
4. Ein Graph ${}G=(V,E)$ heißt starr, wenn die Automorphismengruppe von ${}G$ trivial ist.
5. Zu einem Multigraphen ${}G$ versteht man unter der Laplace-Matrix ${}L$ die Differenz

   ${}L=D-A\,$

   aus Gradmatrix ${}D$ und Adjazenzmatrix ${}A$.

6. Die chromatische Zahl eines Graphen ist die minimale Anzahl an Farben, die man für eine zulässige Färbung benötigt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl in der Potenzmenge zu einer endlichen Menge.
2. Der Satz über die Beschreibung des Durchschnitts von Untergruppen von ${}\mathbb {Z}$.
3. Der Fünf-Farben-Satz.

Lösung

1. Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen. Dann besitzt die Potenzmenge ${}{\mathfrak {P}}\,(M)$ genau ${}2^{m}$ Elemente.
2. Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen. Dann ist

   ${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,,$

   wobei ${}u$ das kleinste gemeinsame Vielfache

   der ${}a_{1},\ldots ,a_{k}$ ist.
3. Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens fünf Farben.

Aufgabe (2 Punkte)

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohl am Ufer eines Flusses und möchte diesen überqueren. Es steht ein Boot zur Verfügung, in dem neben ihm nur ein weiterer Passagier Platz hat. Wie kann er den Fluss überqueren, ohne dass dabei der Wolf die Ziege oder die Ziege den Kohl frisst?

Lösung

1. Er fährt mit der Ziege ans andere Ufer.
2. Er fährt allein zurück.
3. Er fährt mit dem Wolf ans andere Ufer.
4. Er fährt mit der Ziege zurück.
5. Er fährt mit dem Kohl ans andere Ufer.
6. Er fährt allein zurück.
7. Er fährt mit der Ziege ans andere Ufer.

Aufgabe (6 Punkte)

Beweise den Satz über die Wohldefiniertheit der Anzahl einer endlichen Menge.

Lösung

Es seien die bijektiven Abbildungen

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

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Aufgabe 3.28 (Mathematik für Anwender (Osnabrück 2023-2024))  (3) wieder bijektiv ist, ist auch

$\psi ^{-1}\circ \varphi \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

bijektiv. Wir müssen also nur die endlichen Standardmengen ${}{\{1,\ldots ,n\}}$ untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

$\theta \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

vorliegt, dass dann

${}n=k\,$

ist. Dies zeigen wir durch Induktion nach ${}n$. Wenn ${}n=0$ ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch ${}k=0$. Es seien nun ${}n,k$ nicht ${}0$, sodass sie also jeweils einen Vorgänger haben. Es sei ${}m$ der Vorgänger von ${}n$ und ${}\ell$ der Vorgänger von ${}k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

${}z=\theta (n)\in \{1,\ldots ,k\}\,.$

Dann gibt es nach der Herausnahme von ${}n$ bzw. ${}z$ eine bijektive Abbildung

$\{1,\ldots ,m\}={\{1,\ldots ,n\}}\setminus \{n\}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}.$

Nach Lemma 1.2 (Diskrete Mathematik (Osnabrück 2020)) gibt es eine bijektive Abbildung zwischen ${}\{1,\ldots ,\ell \}$ und ${}\{1,\ldots ,k\}\setminus \{z\}$. Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen ${}\{1,\ldots ,m\}$ und ${}\{1,\ldots ,\ell \}$. Nach Induktionsvoraussetzung ist ${}m=\ell$, also auch

${}n=m'=\ell '=k\,.$

Aufgabe (2 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}10$ Cent begleichen?

Lösung

Wir zählen zunächst die Möglichkeiten, mit den ${}5$- und ${}10$-Centmünzen die folgenden Beträge darzustellen:

$0{\text{ Cent}}:1{\text{ Möglichkeit}},$

$5{\text{ Cent}}:1{\text{ Möglichkeit}},$

$10{\text{ Cent}}:2{\text{ Möglichkeiten}}.$

Dann betrachten wir in jedem Fall, mit wie vielen ${}2$-Centmünzen man jeweils noch unterhalb von ${}10$ Cent bleibt, der verbleibende Rest wird mit ${}1$-Centmünzen aufgefüllt. Hierfür gibt es der Reihe nach

$6,3,1{\text{ Möglichkeiten}}.$

Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt

${}1\cdot 6+1\cdot 3+2\cdot 1=11\,$

Möglichkeiten.

Aufgabe (3 (1.5+1.5) Punkte)

Ein Zug fährt ${}100$ Kilometer den Rhein abwärts mit einer Geschwindigkeit von ${}100$ kmh. Auf dem Rhein fahren Schiffe in beide Richtungen, alle mit einer Geschwindigkeit von ${}20$ kmh, wobei sie zu den gleichgerichteten Schiffen einen konstanten Abstand von ${}2$ km einhalten. Zu Beginn der Fahrt ist der Zug gleichauf mit zwei Schiffen (in beide Richtungen).

1. Wie vielen entgegenkommenden Schiffen begegnet der Zug?
2. Wie viele Schiffe überholt der Zug?

Lösung

Wir denken uns die Rheinstrecke skaliert von ${}0$ bis ${}120$, der Startort ist beim Nullpunkt ${}0$ und der Zielpunkt des Zuges ist bei ${}100$. Aufgrund der Anfangsbedingung befinden sich zum Startzeitpunkt Schiffe in beide Richtungen in den Positionen

$0,2,4,\ldots ,98,100,102,\ldots ,118,120.$

1. Die entgegenkommenden Schiffe sind die in Gegenrichtung fahrenden Schiffe, die sich zum Startzeitpunkt an den Positionen ${}0$ bis ${}120$ befinden (das Schiff in der Position ${}120$ ist nach einer Stunde an der Position ${}100$ und begegnet zum Endzeitpunkt dem Zug). Dies sind insgesamt ${}61$ Schiffe.
2. Die eingeholten Schiffe sind die in gleicher Richtung fahrenden Schiffe, die sich zum Startzeitpunkt an den Positionen ${}0$ bis ${}80$ befinden (das Schiff in der Position ${}80$ ist nach einer Stunde an der Position ${}100$ und wird zum Endzeitpunkt vom Zug eingeholt). Dies sind insgesamt ${}41$ Schiffe.

Aufgabe (4 Punkte)

Im Sportunterricht wird ein Zirkeltraining mit den Stationen

Trampolin, Kletterwand, Schwebebalken, Basketballkorb, Laufband, Medizinball

durchgeführt. Bei einem Durchlauf soll die Kletterwand und der Schwebebalken unmittelbar hintereinander absolviert werden (die Reihenfolge ist aber egal), die beiden Ballstationen (Basketballkorb und Medizinball) sollen aber nicht unmittelbar hintereinander absolviert werden.

Wie viele Möglichkeiten (Reihenfolgen) gibt es für einen vollständigen Durchlauf, wenn diese beiden Bedingungen erfüllt sein sollen?

Lösung

Wir betrachten zunächst die unmittelbar hintereinander zu absolvierenden Stationen Kletterwand und Schwebebalken als eine gemeinsame Station „Holz“. Damit gibt es ${}5$ Stationen. Es gibt ${}{\binom {5}{2}}=10$ Möglichkeiten, aus den ${}5$ Positionen ${}2$ Positionen auszusuchen, an denen der Basketballkorb bzw. der Medizinball absolviert wird. Darunter gibt es ${}4$ Möglichkeiten, bei denen beiden Ballstationen direkt hintereinander liegen. Somit gibt es ${}10-4=6$ erlaubte Auswahlen für die Positionen der beiden Ballstationen. Wenn diese festgelegt sind, so gibt es jeweils ${}2$ Möglichkeiten, welche der beiden Ballstationen an welcher Position durchgeführt wird, es gibt ${}3!=6$ Möglichkeiten, in welcher Reihenfolge die drei anderen Stationen (also Trampolin, Laufband und Holz) abgearbeitet werden, und dann gibt es noch jeweils ${}2$ Möglichkeiten für die Reihenfolge innerhalb der Holzstation. Insgesamt gibt es also

${}6\cdot 6\cdot 2\cdot 2=144\,$

erlaubte Reihenfolgen.

Aufgabe (3 Punkte)

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring ${}R$ durch Induktion über ${}k$, wobei der Fall ${}k=2$ verwendet werden darf (dabei sind ${}n_{1},\ldots ,n_{k}$ natürliche Zahlen und ${}a_{j,i}\in R$).

${}{\begin{aligned}{\left(\sum _{i_{1}=1}^{n_{1}}a_{1,i_{1}}\right)}\cdot {\left(\sum _{i_{2}=1}^{n_{2}}a_{2,i_{2}}\right)}\cdots {\left(\sum _{i_{k}=1}^{n_{k}}a_{k,i_{k}}\right)}&=\sum _{(i_{1},i_{2},\ldots ,i_{k})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\\\end{aligned}}$

Lösung

Es sei die Aussage für ein bestimmtes ${}k$ bewiesen. Für ${}k+1$ Faktoren ist dann unter Verwendung der Induktionsvoraussetzung und unter Verwendung des Falles von zwei Faktoren

${}{\begin{aligned}&{\left(\sum _{i_{1}=1}^{n_{1}}a_{1,i_{1}}\right)}\cdot {\left(\sum _{i_{2}=1}^{n_{2}}a_{2,i_{2}}\right)}\cdots {\left(\sum _{i_{k+1}=1}^{n_{k+1}}a_{k+1,i_{k+1}}\right)}\\&={\left(\sum _{(i_{1},i_{2},\ldots ,i_{k})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\right)}{\left(\sum _{i_{k+1}=1}^{n_{k+1}}a_{k+1,i_{k+1}}\right)}\\&={\left(\sum _{(i_{1},i_{2},\ldots ,i_{k},i_{k+1})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}\times \{1,\ldots ,n_{k+1}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\cdot a_{k+1,i_{k+1}}\right)}.\end{aligned}}$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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

Die Karte zeigt Österreich mit seinen Bundesländern und den zugehörigen Hauptstädten (die Hauptstadt des Bundeslandes Wien ist Wien, Tirol ist ein Bundesland). Es sei ${}M$ die Menge der Bundesländer und sei ${}R$ die Relation auf ${}M$, die die Angrenzungsbeziehung (Nachbarschaftsbeziehung) beschreibt. Dabei legen wir fest, dass ein Land auch zu sich selbst benachbart ist.

1. Welche Eigenschaften einer Äquivalenzrelation erfüllt diese Relation?
2. Bestimme die Faser zu Kärnten.
3. Gibt es eine Kette ${}x_{1},x_{2},\ldots ,x_{n}$ in ${}M$ mit ${}x_{i}Rx_{i+1}$ für alle ${}i$, bei der jedes Bundesland genau einmal vorkommt?

Lösung

1. Die Relation ist offenbar symmetrisch und aufgrund der Festlegung auch reflexiv. Sie ist nicht transitiv, da beispielsweise Kärnten und Steiermark und Steiermark und Niederösterreich benachbart sind, aber nicht Kärnten und Niederösterreich.
2. Die Faser zu Kärnten besteht aus Kärnten, Steiermark, Salzburg, Tirol.
3. Das ist möglich: Wien, Niederösterreich, Burgenland, Steiermark, Oberösterreich, Salzburg, Kärnten, Tirol, Vorarlberg.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (4 Punkte)

Beweise das Lemma von Euklid für ganze Zahlen.

Lösung

Wir setzen voraus, dass ${}a$ kein Vielfaches von ${}p$ ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ${}b$ ein Vielfaches von ${}p$ ist. Unter der gegebenen Voraussetzung sind ${}a$ und ${}p$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${}r,s$ mit

${}ra+sp=1\,$

Da ${}ab$ ein Vielfaches von ${}p$ ist, gibt es ein ${}t$ mit

${}ab=tp\,.$

Daher ist

${}b=b\cdot 1=b(ra+sp)=abr+bsp=tpr+bsp=p{\left(tr+bs\right)}\,.$

Also ist ${}b$ ein Vielfaches von ${}p$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Bestimme das inverse Element zu ${}{\overline {55}}$ in ${}\mathbb {Z} /(93)$.

Lösung

Der euklidische Algorithmus liefert

${}93=1\cdot 55+38\,,$

${}55=1\cdot 38+17\,,$

${}38=2\cdot 17+4\,,$

${}17=4\cdot 4+1\,.$

Somit ist

${}{\begin{aligned}1&=17-4\cdot 4\\&=17-4\cdot (38-2\cdot 17)\\&=9\cdot 17-4\cdot 38\\&=9\cdot {\left(55-38\right)}-4\cdot 38\\&=9\cdot 55-13\cdot 38\\&=9\cdot 55-13\cdot {\left(93-55\right)}\\&=22\cdot 55-13\cdot 93.\end{aligned}}$

Daher ist

$22$

das inverse Element zu ${}55$ in ${}\mathbb {Z} /(93)$.

Aufgabe (3 Punkte)

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

$f\colon M\longrightarrow N$

eine surjektive 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. Wegen der Surjektivität ist stets ${}m_{i}\geq 1$. 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 (4 (2+2) Punkte)

Es sei ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus.

1. Es sei ${}\varphi$ injektiv. Zeige, dass für den Grad die Abschätzung

   ${}d(P)\leq d(\varphi (P))\,$

   für jeden Punkt ${}P\in G$ gilt.

2. Wie sieht es aus, wenn ${}\varphi$ nicht injektiv ist?

Lösung

1. Es seien ${}v_{1},\ldots ,v_{n}$ die an ${}P$ anliegenden Punkte, also ${}d(P)=n$. Diese werden auf verschiedene Punkte ${}\varphi (v_{i})$ abgebildet und es ist stets ${}\varphi (P)\varphi (v_{i})$ eine Kante von ${}H$. Also liegen an ${}\varphi (P)$ zumindest ${}n$ Kanten an.
2. Ohne die Voraussetzung injektiv ist die Aussage aus (1) nicht richtig. Betrachten wir den linearen Graphen ${}1,2,3$, also mit den zwei Kanten ${}\{1,2\}$ und ${}\{2,3\}$, und die Abbildung auf den linearen Graphen ${}a,b$, also mit der Kante ${}\{a,b\}$, der ${}1$ und ${}3$ auf ${}a$ und ${}2$ auf ${}b$ abbildet. Da Kanten auf Kanten gehen, liegt ein Graphhomomorphismus vor. Der Grad von ${}2$ ist aber gleich ${}2$, während der Grad von ${}b$ gleich ${}1$ ist.

Aufgabe (3 (1.5+1.5) Punkte)

Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem ${}3\times 3$-Brett wie abgebildet.

1. Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.
2. Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

Lösung

1. Die beiden weißen horizontalen Felder (links bzw. rechts) und die beiden weißen vertikalen Felder (oben bzw. unten) bilden eine bipartite Zerlegung. Bei einem Läuferzug auf diesen weißen Feldern wird stets von einem horizontalen zu einem vertikalen Feld und umgekehrt hinübergewechselt.
2. Betrachten wir die Hauptdiagonale. Der schwarzfeldrige Läufer kann von links unten in die Mitte und dann nach rechts oben und von dort direkt wieder nach links unten ziehen. Dies ist ein Kreis der Länge ${}3$, was es nach Satz 20.8 (Diskrete Mathematik (Osnabrück 2020)) in einem bipartiten Graphen nicht gibt.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (1 Punkt)

Begründe, dass der abgebildete Graph hamiltonsch ist.

Lösung Dürergraph/Hamiltonsch/Aufgabe/Lösung