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	$\sum$
Punkte	3	3	2	6	3	4	3	4	3	3	7	7	4	5	3	4	64

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. Der Typ einer Permutation $\pi$ auf einer endlichen Menge $M$.
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. Man nennt das Tupel

   $(t_1,\dots ,t_k)$

   mit

   $1\le t_1\le t_2\le \dots \le t_k,$

   wobei $k$ die Anzahl der in $\pi$ vorkommenden Zyklen (einschließlich der Fixpunkte) bezeichnet und die $t_j$ die Längen dieser Zyklen bezeichnen, den Typ der Permutation.

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 $𝔓(M)$ genau $2^m$ Elemente.
2. Es seien $a_1,\dots ,a_k$ ganze Zahlen. Dann ist

   $\mathbb{Z}{a}_1\cap \mathbb{Z}{a}_2\cap \dots \cap \mathbb{Z}{a}_k=\mathbb{Z}u,$

   wobei $u$ das kleinste gemeinsame Vielfache

   der $a_1,\dots ,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

$\phi :\{1,\dots ,n\}⟶M$

und

$\psi :\{1,\dots ,k\}⟶M$

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

${\psi }^{-1}\circ \phi :\{1,\dots ,n\}⟶\{1,\dots ,k\}$

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

$\theta :\{1,\dots ,n\}⟶\{1,\dots ,k\}$

vorliegt, 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,\dots ,k\}.$

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

$\{1,\dots ,m\}=\{1,\dots ,n\}\setminus \{n\}⟶\{1,\dots ,k\}\setminus \{z\}.$

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

$n=m^{\prime }={\ell }^{\prime }=k.$

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,\dots ,98,100,102,\dots ,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)

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,\dots ,n_k$ natürliche Zahlen und $a_{j,i}\in R$).

$\begin{array}{cc}\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,\dots ,i_k)\in \{1,\dots ,n_1\}\times \{1,\dots ,n_2\}\times \cdots \times \{1,\dots ,n_k\}}{a}_{1,i_1}\cdot a_{2,i_2}\cdots a_{k,i_k}.\end{array}$

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{array}{cc}& \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)\\ & =(\sum _{(i_1,i_2,\dots ,i_k)\in \{1,\dots ,n_1\}\times \{1,\dots ,n_2\}\times \cdots \times \{1,\dots ,n_k\}}{a}_{1,i_1}\cdot a_{2,i_2}\cdots a_{k,i_k})\left(\sum _{i_{k+1}=1}^{n_{k+1}}{a}_{k+1,i_{k+1}}\right)\\ & =(\sum _{(i_1,i_2,\dots ,i_k,i_{k+1})\in \{1,\dots ,n_1\}\times \{1,\dots ,n_2\}\times \cdots \times \{1,\dots ,n_k\}\times \{1,\dots ,n_{k+1}\}}{a}_{1,i_1}\cdot a_{2,i_2}\cdots a_{k,i_k}\cdot a_{k+1,i_{k+1}}).\end{array}$

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,\dots ,x_n$ in $M$ mit $x_{i}R{x}_{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 (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 Bézout 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(tr+bs).$

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

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{array}{cc}1& =17-4\cdot 4\\ & =17-4\cdot (38-2\cdot 17)\\ & =9\cdot 17-4\cdot 38\\ & =9\cdot (55-38)-4\cdot 38\\ & =9\cdot 55-13\cdot 38\\ & =9\cdot 55-13\cdot (93-55)\\ & =22\cdot 55-13\cdot 93.\end{array}$

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:M⟶N$

eine surjektive Abbildung. Wie viele Abbildungen

$s:N⟶M$

mit

$f\circ s={\mathrm{Id}}_N$

gibt es?

Lösung

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

$M_i=\{x\in M\mid f(x)=i\}$

und

$m_i=\mathrm{\#}\left(M_i\right)=\mathrm{\#}\left(\{x\in M\mid f(x)=i\}\right)$

die Anzahl der Elemente aus $M$, die auf $i$ abgebildet werden. Wegen der Surjektivität ist stets  $m_i\ge 1$.  Da

$f\circ s={\mathrm{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 (7 (3+1+1+2) Punkte)

Es sei ${\sim }_1$ eine Äquivalenzrelation auf einer Menge $M$ und ${\sim }_2$ eine Äquivalenzrelation auf einer Menge $N$, die zueinander mittels der beiden bijektiven Abbildungen

$\phi ,\psi :M⟶N$

isomorph seien. Es gilt also $x{\sim }_{1}y$ (in $M$) genau dann, wenn $\phi (x){\sim }_2\psi (y)$ (in $N$) gilt.

1. Zeige, dass $\phi$ (und ebenso $\psi$) eine Äquivalenzklasse von ${\sim }_1$ in eine Äquivalenzklasse von ${\sim }_2$ abbildet (es gilt also $\phi ([x])=[\phi (x)]$).
2. Zeige, dass $\phi$ und $\psi$ jede Äquivalenzklasse von ${\sim }_1$ in die gleiche Äquivalenzklasse von ${\sim }_2$ abbildet.
3. Man gebe ein Beispiel, wo  $\phi \ne \psi$  ist.
4. Es seien $M,N$ endlich. Zeige, dass die beiden Äquivalenzrelationen sogar konjugiert-isomorph zueinander sind.

Lösung

1. Wegen der Reflexivität von ${\sim }_1$ folgt  $\phi (x){\sim }_2\psi (x)$.  Für ein $y$ mit  $x{\sim }_{1}y$  ist  $\phi (x){\sim }_2\psi (y)$.  Wegen der Transitivität von ${\sim }_2$ ist daher

   $\psi (x){\sim }_2\psi (y).$

   Ebenso folgt daraus mit  $\phi (y){\sim }_2\psi (y)$  auch

   $\phi (x){\sim }_2\phi (y).$

   Beide Abbildungen bilden also eine jede Äquivalenzklasse in eine Äquivalenzklasse ab. Aus  $\phi (x){\sim }_2\phi (y)$  folgt über  $\phi (y){\sim }_2\psi (y)$  zunächst  $\phi (x){\sim }_2\psi (y)$  und dann

   $x{\sim }_{1}y.$

   Das Bild einer Äquivalenzklasse ist also genau eine Äquivalenzklasse.

2. Dies wurde in Teil (1) mitbewiesen.
3. Es sei  $M=N$  eine Menge mit der totalen Äquivalenzrelation  ${\sim }_1={\sim }_2$,  es seien also je zwei Elementen zueinander äquivalent. Dann erfüllen beliebige bijektive Abbildungen $\phi$ und $\psi$ die Voraussetzung.
4. Nach Teil (1) wird die Äquivalenzklasse $[x]$ auf die Äquivalenzklasse $[\phi (x)]$ abgebildet. Weil $\phi$ bijektiv ist, haben diese beiden Klassen die gleiche Anzahl. Daher stimmen überhaupt die Klassenanzahltupel der beiden Äquivalenzrelationen überein, und nach Lemma 15.12 (Diskrete Mathematik (Osnabrück 2026)) sind die Äquivalenzrelationen zueinander konjugiert-isomorph.

Aufgabe (7 (1+1+1+2+2) Punkte)

Wir betrachten die lineare Rekursion  $x_n=3x_{n-1}+7x_{n-2}$. 

a) Erstelle die Rekursionsmatrix zu dieser Rekursion.

b) Bestimme das charakteristische Polynom zu dieser Rekursion.

c) Bestimme die Nullstellen des charakteristischen Polynoms.

d) Bestimme die Eigenvektoren zur Rekursionsmatrix.

e) Bestimme die explizite Lösung zu dieser Rekursion für die Anfangsglieder  $x_0=2$  und  $x_1=-5$. 

Lösung

a) Die Rekursionsmatrix ist

$\left(\begin{array}{cc}3& 7\\ 1& 0\end{array}\right).$

b) Das charakteristische Polynom ist

$det\left(\begin{array}{cc}T-3& -7\\ -1& T\end{array}\right)=T(T-3)-7=T^2-3T-7.$

c) Die Nullstellen des charakteristischen Polynoms sind

${\lambda }_{1,2}=\frac{3\pm \sqrt{37}}{2}.$

d) Eine Basis aus Eigenvektoren ist $\left(\begin{array}{c}\frac{3+\sqrt{37}}{2}\\ 1\end{array}\right)$ und $\left(\begin{array}{c}\frac{3-\sqrt{37}}{2}\\ 1\end{array}\right)$.

e) Wir schreiben

$\left(\begin{array}{c}-5\\ 2\end{array}\right)=a\left(\begin{array}{c}\frac{3+\sqrt{37}}{2}\\ 1\end{array}\right)+b\left(\begin{array}{c}\frac{3-\sqrt{37}}{2}\\ 1\end{array}\right).$

Dieses lineare Gleichungssystem besitzt die Lösung

$\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}\frac{\sqrt{37}-11}{\sqrt{37}}\\ \frac{\sqrt{37}+11}{\sqrt{37}}\end{array}\right).$

Daher ist

$x_n={\left(\frac{3+\sqrt{37}}{2}\right)}^n\frac{\sqrt{37}-11}{\sqrt{37}}+{\left(\frac{3-\sqrt{37}}{2}\right)}^n\frac{\sqrt{37}+11}{\sqrt{37}}$

gemäß Satz 16.6 (Diskrete Mathematik (Osnabrück 2026)) die explizite Lösung.

Aufgabe (4 (2+2) Punkte)

Es sei $\phi :G\to H$ ein Graphhomomorphismus.

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

   $d(P)\le d(\phi (P))$

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

2. Wie sieht es aus, wenn $\phi$ nicht injektiv ist?

Lösung

1. Es seien $v_1,\dots ,v_n$ die an $P$ anliegenden Punkte, also  $d(P)=n$.  Diese werden auf verschiedene Punkte $\phi (v_i)$ abgebildet und es ist stets $\phi (P)\phi (v_i)$ eine Kante von $H$. Also liegen an $\phi (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 (5 (1+1+1+2) Punkte)

Wir betrachten das Kladogramm der Artiodactyla als einen binären Baum $B$.

1. Was ist die Exzentrizität der Wurzel Cetartiodactyla und was ist der Durchmesser von $B$?
2. Was ist der Abstand zwischen einem Wal (Cetacea) und einem Schwein (Suina)?
3. Zeige, dass jeder Graphautomorphismus von $B$ die Wurzel auf sich selbst oder auf die Kamele (Tylopoda) abbildet.
4. Bestimme die Automorphismengruppe von $B$.

Lösung erstellen

Aufgabe (3 (1.5+1.5) Punkte)

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

a) Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.

b) Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

Lösung

a) 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.

b) 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 23.8 (Diskrete Mathematik (Osnabrück 2026)) in einem bipartiten Graphen nicht gibt.

Aufgabe (4 (1+1+1+1) Punkte)

Man gebe ein Beispiel für einen zyklischen zusammenhängenden Graphen $G$, der die folgenden Eigenschaften erfüllt.

1. $G$ ist hamiltonsch und eulersch.
2. $G$ ist hamiltonsch und nicht eulersch.
3. $G$ ist nicht hamiltonsch und eulersch.
4. $G$ ist weder hamiltonsch noch eulersch.

Lösung

1. Ein Rundgang.
2. Der vollständige Graph mit $4$ Knoten ist hamiltonsch, aber nicht eulersch, da die Punkte den Grad $3$ besitzen.

3. 

   Dieser Graph ist nicht hamiltonsch, da der Kreuzungspunkt doppelt durchlaufen werden müsste.

   
   

   
   

   
   

   
   

4. 

   Dieser Graph ist aufgrund des Blattes nicht hamiltonsch und aufgrund des Punktes mit Grad $3$ nicht eulersch.