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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	${}\sum$
Punkte	3	3	2	3	4	3	2	4	4	10	4	3	3	5	4	2	3	2	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein kommutativer Ring ${}R$.
2. Eine Relation auf einer Menge ${}M$.
3. Die Folge der euklidischen Reste zu ganzen Zahlen ${}a,b$ mit  ${}b\neq 0$. 
4. Die Automorphismengruppe eines ungerichteten Graphen ${}G$.
5. Der Umfang eines zyklischen Graphen ${}G$.
6. Eine zulässige Färbung eines Graphen  ${}G=(V,E)$. 

Lösung

1. Ein Ring ${}R$ heißt kommutativ, wenn die Multiplikation kommutativ ist.
2. Eine Relation ${}R$ auf einer Menge ${}M$ ist eine Teilmenge der Produktmenge ${}M\times M$, also  ${}R\subseteq M\times M$. 
3. Man nennt die durch die Anfangsbedingungen ${}r_{0}=a$ und ${}r_{1}=b$ und die mittels der Division mit Rest

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

   rekursiv bestimmte Folge ${}r_{i}$ die Folge der euklidischen Reste.

4. Zu einem Graphen ${}G$ nennt man die Gruppe aller Automorphismen

   $\varphi \colon G\longrightarrow G$

   die Automorphismengruppe von ${}G$.

5. Der Umfang eines zyklischen Graphen ${}G$ ist die längste Länge eines Kreises in ${}G$.
6. Eine Färbung

   $f\colon V\longrightarrow B$

   heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Beziehung zwischen der Addition und endlichen Mengen.
2. Der Satz über die Restklassenkörper von ${}\mathbb {Z}$.
3. Der Rekursionssatz für aufspannende Bäume.

Lösung

1. Es seien ${}M$ und ${}N$ disjunkte endliche Mengen mit ${}m$ bzw. ${}n$ Elementen. Dann besitzt ihre Vereinigung ${}M\cup N$ gerade ${}m+n$ Elemente.
2. Es sei ${}n\in \mathbb {N}$. Der Restklassenring ${}\mathbb {Z} /(n)$ ist genau dann ein Körper, wenn ${}n$ eine Primzahl ist.
3. Es sei ${}G$ ein schleifenfreier Multigraph und ${}e$ eine Kante von ${}G$. Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

   ${}t(G)=t(G\setminus e)+t(G/e)\,.$

Aufgabe (2 Punkte)

Anna kann sich nicht zwischen Heinrich und Konrad entscheiden, deshalb lässt sie sich vom Zufall leiten. Sie wohnt an einer U-Bahn-Station der Linie ${}5$, die von Heinsheim nach Konsau fährt. Heinrich wohnt in Heinsheim und Konrad in Konsau. Wenn Anna Lust auf ein Date hat, geht sie einfach zu ihrer Station und nimmt die erstbeste U-Bahn, die gerade kommt. Die U-Bahnen fahren in beide Richtungen im Zehn-Minuten-Takt und die U-Bahnen nach Heinsheim fahren ${}:\!01,:\!11,:\!21$ etc. Nach einiger Zeit stellt Anna fest, dass sie Konrad viermal so häufig besucht wie Heinrich. Wann fahren die U-Bahnen nach Konsau ab?

Lösung

Die Wahrscheinlichkeit, dass als erstes eine U-Bahn nach Konsau kommt, muss viermal so groß sein wie die Wahrscheinlichkeit, dass zuerst eine U-Bahn nach Heinsheim kommt. Deshalb muss in einem Zehn-Minuten-Intervall acht Minuten lang eine U-Bahn nach Konsau die nächste sein (und zwei Minuten lang eine U-Bahn nach Heinsheim). Die U-Bahnen nach Konsau fahren also ${}:\!09,:\!19,:\!29$ etc. ab.

Aufgabe (3 Punkte)

Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?

Lösung

Das Pickelpaar und die drei übrigen einzelnen Pickel können als vier Pickelfelder betrachtet werden, die in beliebiger Reihenfolge beackert werden können. Dafür gibt es ${}4!=24$ Möglichkeiten. Bei jeder dieser Reihenfolge hat man beim Pickelpaar die freie Wahlmöglichkeit, welcher zuerst drankommt. Daher gibt es insgesamt

${}2\cdot 24=48\,$

Möglichkeiten.

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

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(n,k)\longmapsto {\binom {n}{k}},$

wobei bei  ${}k>n$  der Binomialkoeffizient als ${}0$ zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

a) Bestimme ${}{\binom {\binom {3}{2}}{1}}$ und ${}{\binom {3}{\binom {2}{1}}}$.

b) Besitzt diese Verknüpfung ein neutrales Element von links?

c) Besitzt diese Verknüpfung ein neutrales Element von rechts?

d) Ist diese Verknüpfung assoziativ?

Lösung

a) Es ist

${}{\binom {\binom {3}{2}}{1}}={\binom {3}{1}}=3\,$

und

${}{\binom {3}{\binom {2}{1}}}={\binom {3}{2}}=3\,.$

b) Es kann kein neutrales Element von links geben, da für  ${}k>n$  gilt

${}{\binom {n}{k}}=0\neq k\,.$

c) ${}1$ ist das neutrale Element von rechts. Für  ${}n\geq 1$  ist

${}{\binom {n}{1}}=n\,$

und dies gilt auch für  ${}n=0$. 

d) Die Verknüpfung ist nicht assoziativ, beispielsweise ist

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

aber

${}{\binom {4}{\binom {3}{2}}}={\binom {4}{3}}=4\,.$

Aufgabe (3 Punkte)

Es sei ${}M$ ein Monoid,  ${}a,b\in M$  und  ${}m,n\in \mathbb {N}$.  Zeige die folgenden Potenzgesetze.

1. ${}a^{m+n}=a^{m}\cdot a^{n}\,.$

2. ${}(a^{m})^{n}=a^{mn}\,.$

3. Wenn ${}M$ kommutativ ist, so ist

   ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,.$

Lösung erstellen

Aufgabe (2 Punkte)

Bestimme für das Polynom

${}P=7X^{11}-3X^{8}+{\frac {3}{2}}X^{6}-X+5\,$

den Grad, den Leitkoeffizienten, den Leitterm und den Koeffizienten zu ${}X^{5}$.

Lösung

Der Grad ist ${}11$, der Leitkoeffizient ist ${}7$, der Leitterm ist ${}7X^{11}$ und der Koeffizient zu ${}X^{5}$ ist ${}0$.

Aufgabe (4 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}5371400$ und ${}695700$.

Lösung

Es ist offenbar ${}100$ ein gemeinsamer Teiler der beiden Zahlen, deshalb bestimmen wir den größten gemeinsamen Teiler von ${}53714$ und ${}6957$. Der Euklidische Algorithmus liefert:

$53714=7\cdot 6957+5015$

$6957=1\cdot 5015+1942$

$5015=2\cdot 1942+1131$

$1942=1\cdot 1131+811$

$1131=1\cdot 811+320$

$811=2\cdot 320+171$

$320=1\cdot 171+149$

$171=1\cdot 149+22$

$149=6\cdot 22+17$

$22=1\cdot 17+5$

$17=3\cdot 5+2$

$5=2\cdot 2+1$

$2=2\cdot 1+0.$

Daher sind die beiden um ${}100$ gekürzten Zahlen teilerfremd und der größte gemeinsame Teiler der beiden Ausgangszahlen ist ${}100$.

Aufgabe (4 Punkte)

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Ordnung auf ${}M$. Zeige durch Induktion über ${}n\geq 2$ die Aussage: Wenn für Elemente ${}a_{1},\ldots ,a_{n}\in M$ die Beziehungen

${}a_{1}\preccurlyeq a_{2}\preccurlyeq \ldots \preccurlyeq a_{n-1}\preccurlyeq a_{n}\,$

und

${}a_{n}\preccurlyeq a_{1}\,$

gelten, dann sind alle ${}a_{1},\ldots ,a_{n}$ gleich.

Lösung

Der Induktionsanfang  ${}n=2$  folgt unmittelbar aus der Antisymmetrie. Es sei also die Aussage für ein gewisses ${}n\geq 2$ schon bewiesen und es liegen ${}n+1$ Elemente mit den Abschätzungen

${}a_{1}\preccurlyeq a_{2}\preccurlyeq \ldots \preccurlyeq a_{n}\preccurlyeq a_{n+1}\,$

und

${}a_{n+1}\preccurlyeq a_{1}\,$

vor. Wegen der Transitivität der Ordnung gilt dann auch

${}a_{n}\preccurlyeq a_{1}\,$

und damit gelten auch die Bedingungen in der Induktionsvoraussetzung. Somit ist also

${}a_{1}=a_{2}=\ldots =a_{n}\,.$

Wegen

${}a_{n}\preccurlyeq a_{n+1}\,$

und

${}a_{n+1}\preccurlyeq a_{1}\,$

stimmt auch ${}a_{n+1}$ mit diesem Element überein.

Aufgabe (10 (3+3+4) Punkte)

Wir betrachten die Menge der natürlichen Zahlen mit den beiden Verknüpfungen

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto {\operatorname {GgT} \,\left(a,b\right)}$

und

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto {\operatorname {KgV} \,\left(a,b\right)}.$

1. Zeige, dass der größte gemeinsame Teiler eine kommutative und assoziative Verknüpfung ist, die ein neutrales Element besitzt (der größte gemeinsame Teiler von ${}0$ und ${}0$ sei als ${}0$ festgelegt).
2. Zeige, dass das kleinste gemeinsame Vielfache eine kommutative und assoziative Verknüpfung ist, die ein neutrales Element besitzt (das kleinste gemeinsame Vielfache von ${}a$ und ${}0$ sei als ${}0$ festgelegt).
3. Zeige, dass mit diesen Verknüpfungen (mit dem GgT als Addition) ein kommutativer Halbring vorliegt.

Lösung

1. Die Kommutativität ist klar. Die ${}0$ ist das neutrale Element, da stets

   ${}{\operatorname {GgT} \,\left(a,0\right)}=a\,,$

   da ja jede Zahl die ${}0$ teilt und somit der größte Teiler von ${}a$ entscheidend ist, und bei ${}a=0$ der Wert des GgT nach Definition ${}0$ ist. Zum Nachweis der Assoziativität ist

   ${}{\operatorname {GgT} \,\left({\operatorname {GgT} \,\left(a,b\right)},c\right)}={\operatorname {GgT} \,\left(a,{\operatorname {GgT} \,\left(b,c\right)}\right)}\,$

   zu zeigen. Wenn eine der beteiligten Zahlen ${}0$ ist, so kommt links und rechts das gleiche heraus. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Wenn die Zahlen durch ihre Primfaktorzerlegung gegeben sind, so ist der größte gemeinsame Teiler durch das Minimum der Exponenten gegeben. Da sich das Minimum assoziativ verhält, gilt auch für den GgT die Assoziativität.

2. Die Kommutativität ist klar. Die ${}1$ ist das neutrale Element, da stets

   ${}{\operatorname {KgV} \,\left(a,1\right)}=a\,,$

   da ja jede Zahl ein Vielfaches der ${}1$ ist. Zum Nachweis der Assoziativität ist

   ${}{\operatorname {KgV} \,\left({\operatorname {KgV} \,\left(a,b\right)},c\right)}={\operatorname {KgV} \,\left(a,{\operatorname {KgV} \,\left(b,c\right)}\right)}\,$

   zu zeigen. Wenn eine der beteiligten Zahlen ${}0$ ist, so kommt links und rechts ${}0$ heraus, da ${}0$ das einzige Vielfache der ${}0$ ist. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Wenn die Zahlen durch ihre Primfaktorzerlegung gegeben sind, so ist das kleinste gemeinsame Vielfache durch das Maximum der Exponenten gegeben. Da sich das Maximum assoziativ verhält, gilt auch für das KgV die Assoziativität.

3. Es ist

   ${}{\operatorname {KgV} \,\left(a,{\operatorname {GgT} \,\left(b,c\right)}\right)}={\operatorname {GgT} \,\left({\operatorname {KgV} \,\left(a,b\right)},{\operatorname {KgV} \,\left(a,c\right)}\right)}\,$

   zu zeigen. Bei ${}a=0$ steht beidseitig ${}0$, da das KgV der ${}0$ mit einer beliebigen Zahl stets ${}0$ ist. Bei ${}b=0$ (analog $c=0$) ergibt sich beidseitig ${}{\operatorname {KgV} \,\left(a,c\right)}$. Wir können also annehmen, dass alle Zahlen ungleich ${}0$ sind. Da sowohl das GgT als auch das KgV aus der Primfaktorzerlegung ablesbar sind, können wir uns auf einen einzigen Primfaktor beschränken. Sei

   ${}a=p^{k}\,,$

   ${}b=p^{m}\,$

   und

   ${}c=p^{n}\,.$

   Dann ist

   ${}\operatorname {max} (k,\operatorname {min} (m,n))=\operatorname {min} (\operatorname {max} (k,m),\operatorname {max} (k,n))\,$

   zu zeigen. Da die Aussage symmetrisch in ${}m$ und ${}n$ ist, können wir

   ${}m\leq n\,$

   annehmen. Dann steht links das Maximum von ${}k$ und ${}m$ und rechts ist jedenfalls

   ${}\operatorname {max} (k,m)\leq \operatorname {max} (k,n)\,,$

   sodass das Minimum davon ebenfalls das Maximum von ${}k$ und ${}m$ ist.

Aufgabe (4 Punkte)

Es sei ${}G$ eine Gruppe. Betrachte die Relation ${}\sim$ auf ${}G$, die durch

$x\sim y{\text{ genau dann, wenn }}x=y{\text{ oder }}x=y^{-1}$

erklärt ist. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Lösung

Die Relation ist offenbar reflexiv. Zum Nachweis der Symmetrie sei ${}x\sim y$. Im Fall ${}x=y$ ist natürlich auch ${}y=x$ und somit ${}y\sim x$. Im Fall

${}x=y^{-1}\,$

ergibt sich durch Invertieren der Gleichung

${}x^{-1}=\left(y^{-1}\right)^{-1}=y\,,$

also ebenfalls ${}y\sim x$. Zum Nachweis der Transitivität sei ${}x\sim y$ und ${}y\sim z$. Hier gibt es insgesamt vier Fälle. Bei ${}x=y$ und ${}y=z$ ist natürlich ${}x=z$. Bei ${}x=y$ und ${}y=z^{-1}$ ist ${}x=z^{-1}$, also ${}x\sim z$. Bei ${}x=y^{-1}$ und ${}y=z$ ist ${}x=y^{-1}=z^{-1}$, also wieder ${}x\sim z$. Bei ${}x=y^{-1}$ und ${}y=z^{-1}$ ist

${}x=y^{-1}=\left(z^{-1}\right)^{-1}=z\,,$

also ${}x\sim z$.

Aufgabe (3 (2+1) Punkte)

Es sei ${}G$ eine endliche Gruppe mit ${}n$ Elementen, wir betrachten die Verknüpfungsabbildung

$\mu \colon G\times G\longrightarrow G,\,(x,y)\longmapsto \mu (x,y)=x\circ y.$

1. Bestimme das Faseranzahltupel von ${}\mu$.
2. Sind die Verknüpfungsabbildungen zu zwei endlichen Gruppen mit der gleichen Anzahl isomorph?

Lösung

1. Zu jedem  ${}z\in G$  besteht die Faser über ${}z$ zur Verknüpfungsabbildung ${}\mu \colon G\times G\rightarrow G$ aus den Elementen ${}\left\{\left(x,x^{-1}z\right)\mid x\in G\right\}$. Das sind also ${}n$ Elemente und deshalb ist das Faseranzahltupel gleich ${}(n,n,\ldots ,n)$.
2. Dies folgt unmittelbar aus (1) und Satz 15.5 (Diskrete Mathematik (Osnabrück 2026)).

Aufgabe (3 Punkte)

Beweise den Satz über die explizite Lösung einer Matrixrekursion im diagonalisierbaren Fall.

Lösung

Wir beweisen die Aussage durch Induktion über ${}n$, der Fall  ${}n=0$  ist die Startsituation. Der Induktionsschritt ergibt sich direkt aus

${}{\begin{aligned}v_{n+1}&=Mv_{n}\\&=M\left(\sum _{i=1}^{d}\lambda _{i}^{n}s_{i}w_{i}\right)\\&=\sum _{i=1}^{d}\lambda _{i}^{n}s_{i}M\left(w_{i}\right)\\&=\sum _{i=1}^{d}\lambda _{i}^{n}s_{i}\lambda _{i}w_{i}\\&=\sum _{i=1}^{d}\lambda _{i}^{n+1}s_{i}w_{i}.\end{aligned}}$

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

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen und sei  ${}k\leq n$.  Es sei  ${}V={\mathfrak {P}}_{k}\,(M)$  die Menge aller ${}k$-elementigen Teilmengen von ${}M$. Zu dieser Knotenmenge machen wir einen Graphen, indem wir zwei solche Teilmengen miteinander durch eine Kante verbinden, wenn die Teilmengen einen nichtleeren Durchschnitt besitzen.

1. Bestimme die Anzahl von ${}V$.
2. Bestimme den Grad von ${}G$ in jedem Punkt.
3. Bestimme die Anzahl der Kanten in diesem Graphen.
4. Zeige, dass der Graph regulär ist.

Lösung

1. Das ist einfach ${}{\binom {n}{k}}$.
2. Es sei eine ${}k$-elementige Teilmenge  ${}T\subseteq M$  fixiert. Diese ist genau dann mit einer weiteren ${}k$-elementigen Teilmenge  ${}S\subseteq M$  nicht durch eine Kante verbunden, wenn  ${}S\subseteq M\setminus T$  ist. Davon gibt es ${}{\binom {n-k}{k}}$ Stück. Somit ist ${}T$ mit

   ${\binom {n}{k}}-{\binom {n-k}{k}}-1$

   Knotenpunkten durch eine Kante verbunden, und dies ist der Grad.

3. Die Anzahl der Kanten ist nach Lemma 18.16 (Diskrete Mathematik (Osnabrück 2026)) gleich

   ${\frac {1}{2}}{\binom {n}{k}}\left({\binom {n}{k}}-{\binom {n-k}{k}}-1\right).$

4. Dies folgt unmittelbar aus Teil (2).

Aufgabe (4 Punkte)

Zeige, dass es in einem Graphen  ${}G=(V,E)$  mit  ${}{\#\left(V\right)}\geq 2$  stets zwei Punkte gibt, deren Grad übereinstimmt.

Lösung

Es sei

${}{\#\left(V\right)}=n\,,$

wir betrachten die Gradabbildung

$d\colon V\longrightarrow \{0,1,\ldots ,n-1\},\,v\longmapsto d(v).$

Der Zielbereich ist dabei richtig gewählt, da ja jeder Punkt höchstens mit jedem anderen Punkt in Verbindung steht. Wir machen eine Fallunterscheidung.

Fall 1. Im Graphen gibt es einen isolierten Punkt. Dann kommt der Wert ${}n-1$ in der Gradabbildung nicht vor, jeder Punkt ist höchstens mit ${}n-2$ Punkten verbunden. Dann kann man die Zielmenge durch ${}\{0,1,\ldots ,n-2\}$ ersetzen, die ${}n-1$ Elemente besitzt, und die Aussage folgt aus dem Schubfachprinzip.

Fall 2. Im Graphen gibt es keinen isolierten Punkt. Dann kann man die Zielmenge durch ${}\{1,\ldots ,n-1\}$ ersetzen, die wieder ${}n-1$ Elemente besitzt, und die Aussage folgt aus dem Schubfachprinzip.

Aufgabe (2 Punkte)

Bestimme für einen linearen Graphen mit ${}n$ Knotenpunkten den Radius und den Durchmesser.

Lösung

Sei der lineare Graph ${}G$ gegeben als

$v_{1}-v_{2}-\cdots -v_{n}.$

Dann ist die Exzentrizität eines Knotens ${}v_{i}$ gegeben durch

${}e(v_{i})={\begin{cases}n-i,{\text{ falls }}i\leq {\frac {n}{2}}\,,\\i-1,{\text{ falls }}i>{\frac {n}{2}}\,,\end{cases}}\,$

also ist der Radius gegeben als

${}\operatorname {min} \left(e(v_{i}){|}i\in \{1,\dots ,n\}\right)=\lfloor {\frac {n}{2}}\rfloor \,$

und der Durchmesser ist

${}\operatorname {max} \left(e(v_{i}){|}i\in \{1,\dots ,n\}\right)=n-1\,.$

Aufgabe (3 Punkte)

Beweise den Satz über Blätter an einem Baum.

Lösung

Wir betrachten die Menge aller Wege ohne Kantenwiederholungen. Da es in ${}G$ keine Kreise gibt, gibt es in einem solchen Weg auch keine Knotenwiederholung. Somit haben alle diese Wege eine (durch ${}{\#\left(V\right)}$) beschränkte Länge. Wir betrachten einen Weg, der unter diesen Wegen in ${}G$ maximale Länge besitzt. Dann sind die Endpunkte Blätter, da man andernfalls den Weg verlängern könnte.

Aufgabe (2 (1+1) Punkte)

Es seien  ${}G_{1}=\left(V_{1},E_{1}\right)$  und  ${}G_{2}=\left(V_{2},E_{2}\right)$  Graphen mit der disjunkten Vereinigung  ${}G=G_{1}\uplus G_{2}$. 

1. In welcher Beziehung steht die Adjazenzmatrix ${}A$ zu ${}G$ zu den Adjazenzmatrizen ${}A_{1}$ und ${}A_{2}$ zu ${}G_{1}$ und ${}G_{2}$?
2. In welcher Beziehung steht das charakteristische Polynom zu ${}G$ zu den charakteristischen Polynomen zu ${}G_{1}$ und ${}G_{2}$?

Lösung

1. Die Adjazenzmatrix ${}A$ ist die Blockmatrix aus den Blöcken ${}A_{1}$ und ${}A_{2}$, die in der Diagonalen stehen, ergänzt um Nullblöcke.
2. Das charakteristische Polynom zu ${}G$ ist aufgrund von Teil (1) das Produkt der beiden charakteristischen Polynome.