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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein inverses Element zu einem Element ${}x\in M$ bezüglich einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

   mit einem neutralen Element ${}e\in M$.

2. Eine lineare (oder totale) Ordnung ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Ein distributiver Verband ${}M$.
4. Ein ungerichteter Graph auf einer Menge ${}V$.
5. Eine Basis in einem Matroid ${}{\mathcal {M}}$.
6. Ein alternierender Weg bezüglich einer Paarung ${}P$ eines Graphen  ${}G=(V,E)$. 

Lösung

1. Zu ${}x\in M$ heißt ${}y\in M$ inverses Element, wenn die Gleichheit

   ${}x\circ y=e=y\circ x\,$

   gilt.

2. Eine Ordnungsrelation ${}\preccurlyeq$ auf ${}I$ heißt lineare Ordnung, wenn zu je zwei Elementen ${}x,y\in I$ die Beziehung ${}x\preccurlyeq y$ oder ${}y\preccurlyeq x$ gilt.
3. Ein Verband ${}M$ heißt distributiv, wenn in ihm die Distributivgesetze

   ${}x\sqcap \left(y\sqcup z\right)=\left(x\sqcap y\right)\sqcup \left(x\sqcap z\right)\,$

   und

   ${}x\sqcup \left(y\sqcap z\right)=\left(x\sqcup y\right)\sqcap \left(x\sqcup z\right)\,$

   gelten.

4. Ein ungerichteter Graph auf ${}V$ ist eine Auswahl an zweielementigen Teilmengen von ${}V$.
5. Eine Basis ist eine maximale Menge in ${}{\mathcal {M}}$.
6. Man nennt einen Weg in ${}G$ alternierend bezüglich der gegebenen Paarung, wenn er abwechselnd Kanten aus ${}P$ und aus ${}E\setminus P$ besitzt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von Abbildungen zwischen endlichen Mengen.
2. Der Satz über die Nichtnullteilereigenschaft in einem Körper ${}K$.
3. Der Charakterisierungssatz für eulersche Graphen.

Lösung

1. Es seien ${}L$ und ${}M$ endliche Mengen mit ${}\ell$ bzw. ${}m$ Elementen. Dann gibt es ${}m^{\ell }$ Abbildungen von ${}L$ nach ${}M$.
2. Aus ${}a\cdot b=0$ mit ${}a,b\in K$ folgt ${}a=0$ oder ${}b=0$.
3. Für einen zusammenhängenden Graphen  ${}G=(V,E)$  sind folgende Aussagen äquivalent.
   1. ${}G$ ist eulersch.
   2. Jeder Knotenpunkt von ${}G$ hat einen geraden Grad.
   3. ${}G$ ist die Vereinigung von kantendisjunkten Kreisen (wobei ein einzelner Punkt hier als Kreis gelte).

Aufgabe (5 Punkte)

Es sei ${}G$ eine Menge, die als disjunkte Vereinigung

${}G=A\uplus B\,$

gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge ${}{\mathfrak {P}}\,(G)$ und der Produktmenge ${}{\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)$.

Lösung

Wir betrachten die Abbildungen

$\varphi \colon {\mathfrak {P}}\,(G)\longrightarrow {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B),\,T\longmapsto (T\cap A,T\cap B),$

und

$\psi \colon {\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)\longrightarrow {\mathfrak {P}}\,(G),\,(U,V)\longmapsto U\cup V,$

und behaupten, dass diese beiden Abbildungen zueinander invers sind. Die Verknüpfung ${}\psi \circ \varphi$ sendet insgesamt eine Teilmenge ${}T\subseteq G$ auf

$(T\cap A)\cup (T\cap B).$

Die Inklusion

${}(T\cap A)\cup (T\cap B)\subseteq T\,$

ist dabei klar. Wenn umgekehrt ${}x\in T$ liegt, so ist aufgrund der Voraussetzung ${}x\in A$ oder ${}x\in B$ und damit ist auch ${}x\in (T\cap A)\cup (T\cap B)$. Daher ist ${}\psi \circ \varphi$ die Identität.

Die Verknüpfung ${}\varphi \circ \psi$ sendet insgesamt ein Paar ${}(U,V)$ bestehend aus Teilmengen ${}U\subseteq A$ und ${}V\subseteq B$ auf

$((U\cup V)\cap A,(U\cup V)\cap B).$

Wir behaupten

${}(U\cup V)\cap A=U\,$

(und entsprechend für die zweite Komponente). Dabei ist die Inklusion ${}\supseteq$ klar. Wenn umgekehrt ${}x\in (U\cup V)\cap A$ ist, so ist ${}x\in A$ und ${}x\in U\cup V$. Wegen ${}V\subseteq B$ und der Disjunktheit von ${}B$ und ${}A$ kann nicht ${}x$ zu ${}V$ gehören, also ist ${}x\in U$. Daher ist auch ${}\varphi \circ \psi$ die Identität.

Aufgabe (8 (1+1+1+3+2) Punkte)

Zur großen Pause fährt der Eiswagen „Largo Maggiore“ auf den Pausenhof. Eisverkäufer Lorenzo di Napoli bietet ${}10$ Eissorten an. Lucy Sonnenschein hat heute Lust auf ein Eis mit drei Kugeln, die in der Eistüte übereinander gestapelt werden.

1. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge mitberücksichtigt wird?
2. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge nicht mitberücksichtigt wird?
3. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge mitberücksichtigt wird?
4. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge nicht mitberücksichtigt wird?
5. Wie kann man mit den Schritten mit denen man (4) beantwortet hat die Antworten zu (1) und zu (3) herleiten?

Lösung

1. Es gibt ${}10\cdot 9\cdot 8=720$ Möglichkeiten, da es für die erste Kugel ${}10$, für die nächste ${}9$, da diese von einer anderen Sorte als die erste sein muss, und für die dritte ${}8$ Möglichkeiten.
2. Es geht um die Anzahl der dreielementigen Teilmengen aus der zehnelementigen Eissortenmenge, also gibt es

   ${}{\binom {10}{3}}={\frac {10\cdot 9\cdot 8}{3\cdot 2\cdot 1}}=120\,$

   Möglichkeiten.

3. Für jede Kugel gibt es zehn Möglichkeiten, die Gesamtzahl ist also

   ${}10^{3}=1000\,.$

4. Wenn sie drei verschiedene Kugeln kauft, so sind das, wie unter (2) berechnet, ${}120$ Möglichkeiten. Wenn sie zwei verschiedene Kugeln kauft, so gibt es für die Auswahl der Sorten

   ${}{\binom {10}{2}}={\frac {10\cdot 9}{2\cdot 1}}=45\,$

   Möglichkeiten. Sodann muss man dabei aber noch festlegen, welche Sorte einmal und welche zweimal genommen wird. Daher gibt es hier ${}90$ Möglichkeiten. Wenn sie von einer Sorte drei Kugeln kauft, so gibt es dafür ${}10$ Möglichkeiten. Insgesamt gibt es also

   ${}120+90+10=220\,$

   Möglichkeiten.

5. Für die ${}120$ Möglichkeiten aus dem ersten Typ von (4) gibt es jeweils sechs Möglichkeiten, in welcher Reihenfolge sie aufgetürmt werden können, das macht die ${}720$ aus Teil (1). Für die ${}90$ Möglichkeiten aus dem zweiten Typ von (4) gibt es jeweils drei Möglichkeiten, in welcher Reihenfolge sie aufgetürmt werden können (an welcher Stelle kommen die einzelnen Kugeln?), das macht ${}270$ Möglichkeiten. Für den dritten Typ aus (4) ist die Reihenfolge unerheblich, es bleibt also bei den ${}10$ Möglichkeiten. Insgesamt ergeben sich so gerechnet

   ${}720+270+10=1000\,,$

   was dem Ergebnis aus Teil (3) entspricht.

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

1. Skizziere vier Geraden im Raum mit der Eigenschaft, dass es insgesamt zwei Schnittpunkte gibt.
2. Skizziere vier Geraden in der Ebene mit der Eigenschaft, dass es insgesamt drei Schnittpunkte gibt.
3. Zeige, dass es in der Ebene nicht vier Geraden geben kann, die insgesamt zwei Schnittpunkte besitzen.

Lösung

1. ${}\,$

2. 

   ${}\,$

3. Es sei angenommen, dass es eine solche Geradenkonfiguration gibt. Wir behandeln die beiden Fälle, dass die beiden Schnittpunkte auf einer der Geraden ${}G$ liegen oder nicht. Im ersten Fall müssen die Geraden, die mit ${}G$ die Schnittpunkte definieren, zueinander parallel sein. Die vierte Gerade kann weder zu ${}G$ noch zu den beiden anderen Geraden parallel sein, sonst würde es neue Schnittpunkte geben. Damit schneidet die vierte Gerade die ersten drei Geraden, und dabei kann zwar ein Schnittpunkt mit den beiden Schnittpunkten zusammenfallen, aber nicht mit beiden. Im zweiten Fall gibt es zwei Geradenpaare, die jeweils die beiden Schnittpunkte definieren. Doch dann trifft jede Gerade zumindest eine Gerade des anderen Geradenpaares in einem neuen Schnittpunkt, da sie nicht zu beiden parallel sein kann und nicht durch deren Schnittpunkt verläuft (sonst wären wir im ersten Fall).

Aufgabe (2 Punkte)

Beweise den Satz über das inverse Element in einer Gruppe ${}(G,\circ ,e)$.

Lösung

Es sei

${}x\circ y=y\circ x=e\,$

und

${}x\circ z=z\circ x=e\,.$

Dann ist

${}y=y\circ e=y\circ (x\circ z)=(y\circ x)\circ z=e\circ z=z\,.$

Aufgabe (1 Punkt)

Bestimme die Primfaktorzerlegung von

${\binom {15}{5}}.$

Lösung

Es ist

${}{\binom {15}{5}}={\frac {15\cdot 14\cdot 13\cdot 12\cdot 11}{5\cdot 4\cdot 3\cdot 2\cdot 1}}={\frac {14\cdot 13\cdot 12\cdot 11}{4\cdot 2}}={\frac {7\cdot 13\cdot 3\cdot 11}{1}}=3\cdot 7\cdot 11\cdot 13\,.$

Aufgabe (7 Punkte)

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von ${}a$ und der andere ein Fassungsvermögen von ${}b$ Litern, wobei ${}a$ und ${}b$ teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Lösung

Ohne Einschränkung sei  ${}a\leq b$.  Wir bezeichnen die Inhalte in den Eimern zu einem bestimmten Zeitpunkt in Paarschreibweise mit ${}(u,v)$, wobei ${}u$ zwischen ${}0$ und ${}a$ und ${}v$ zwischen ${}0$ und ${}b$ liegt. Es sei ${}r$ der Rest von ${}-b$ bei Division durch ${}a$. Wir behaupten, dass wenn man die Belegung ${}(u,0)$ durch die erlaubten Schritte erzielen kann, dass man dann auch ${}(u',0)$ erzielen kann, wobei ${}u'$ den Rest von ${}u+r$ modulo ${}a$ bezeichnet. Wir starten also mit

$(u,0).$

Durch Umschüttung kann man

$(0,u)$

erreichen. Durch Auffüllen des kleinen Eimers und anschließende Umfüllung in den großen kann man

$(0,u+a)$

erreichen, und ebenso der Reihe nach

$(0,u+2a),\,(0,u+2a),\ldots ,(0,u+ka),$

wobei ${}k$ so gewählt sei, dass

${}u+ka\leq b\,$

und

${}u+(k+1)a>b\,$

sei. Von hier aus erreichen wir

$(a,u+ka).$

Wir füllen nun den Inhalt des ersten Eimers in den zweiten, bis dieser voll ist. Es sei ${}m$ die umgefüllte Menge. Diese erfüllt

${}u+ka+m=b\,.$

Die im ersten Eimer verbleibende Wassermenge ist somit

${}a-m=a-(b-u-ka)=u+(k+1)a-b\,.$

Diese Menge ist also der Rest von  ${}u-b=u+r$  modulo ${}a$, wie behauptet.

Aufgrund von dieser Beobachtung können wir der Reihe nach folgende Belegungen erzielen (bzw. die Reste davon modulo a).

$(0,0),(r,0),(2r,0),(3r,0),\ldots .$

Da ${}b$ teilerfremd zu ${}a$ ist, gibt es nach dem Lemma von Bézout positive ganze Zahlen ${}n,m$ mit

${}ma-nb=1\,$

(Falls ${}n,m$ negativ sind, betrachtet man einfach ${}(sb+m)a-(sa+n)b=1$ für ein ausreichend großes ${}s$).

Somit ist modulo ${}a$

${}nr\equiv -nb=1-ma=1\,,$

sodass bei Division durch ${}a$ für ein gewisses ${}n$ der Rest von ${}nr$ gleich ${}1$ ist.

Aufgabe (6 Punkte)

Beweise den Satz über die atomare Darstellung in einem booleschen Verband.

Lösung

Jedes Element  ${}x\in B$  ist nur größergleich endlich vielen Atomen, wir führen zum Nachweis der Existenz Induktion über diese Anzahl. Bei  ${}x=0$  nimmt man die leere Vereinigung. Ein Atom wird durch sich selbst dargestellt. Es sei  ${}x\neq 0$  ein beliebiges Element. Nach Lemma 9.20 (Diskrete Mathematik (Osnabrück 2026))  (3) gibt es ein Atom  ${}a\preccurlyeq x$.  Wir betrachten

${}x'=x\sqcap \neg a\,.$

Wegen

${}x'\sqcap a=(x\sqcap \neg a)\sqcap a=x\sqcap (\neg a\sqcap a)=x\sqcap 0=0\,$

liegt ${}a$ nicht unterhalb von ${}x'$. Somit liegen unterhalb von ${}x'$ weniger Atome als unterhalb von ${}x$ und nach Induktionsvoraussetzung gibt es eine Darstellung

${}x'=a_{1}\sqcup \ldots \sqcup a_{n}\,$

und damit

${}{\begin{aligned}x&=x\sqcap 1\\&=x\sqcap (\neg a\sqcup a)\\&=(x\sqcap \neg a)\sqcup (x\sqcap a)\\&=(x\sqcap \neg a)\sqcup a\\&=x'\sqcup a\\&=a_{1}\sqcup \ldots \sqcup a_{n}\sqcup a.\end{aligned}}$

Zur Eindeutigkeit. Sei

${}a_{1}\sqcup \ldots \sqcup a_{n}=b_{1}\sqcup \ldots \sqcup b_{m}\,.$

Nehmen wir an, dass ${}b_{1}$ nicht in der ersten Darstellung vorkommt. Dann ist

${}\left(a_{1}\sqcup \ldots \sqcup a_{n}\right)\sqcap b_{1}=(a_{1}\sqcap b_{1})\sqcup \ldots \sqcup (a_{n}\sqcap b_{1})=0\,$

nach Lemma 9.20 (Diskrete Mathematik (Osnabrück 2026))  (2). Wenn man aber auf die rechte Seite ${}\sqcap b_{1}$ anwendet, so ergibt sich ${}b_{1}$, ein Widerspruch. Also kommen links und rechts die gleichen Atome vor.

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

Es sei ${}\leq _{1}$ eine Ordnungsrelation auf einer Menge ${}M_{1}$ und ${}\leq _{2}$ eine Ordnungsrelation auf einer Menge ${}M_{2}$, die zueinander mittels der beiden bijektiven Abbildungen

$\varphi ,\psi \colon M_{1}\longrightarrow M_{2}$

isomorph seien. Es gilt also ${}x\leq _{1}y$ (in ${}M_{1}$) genau dann, wenn ${}\varphi (x)\leq _{2}\psi (y)$ (in ${}M_{2}$) gilt.

1. Zeige, dass ${}\varphi$ ordnungstreu ist.
2. Zeige, dass ${}\varphi$ ordnungsvolltreu ist.
3. Zeige, dass ${}\left(M_{1},\leq _{1}\right)$ und ${}\left(M_{2},\leq _{2}\right)$ zueinander konjugiert-isomorph sind.

Lösung

1. Es sei  ${}x\leq _{1}y$.  Da ${}\psi$ bijektiv ist, gibt es ein  ${}u\in M_{1}$  mit  ${}\varphi (y)=\psi (u)$.  Insbesondere gilt

   ${}\varphi (y)\leq _{2}\psi (u)\,$

   und daher gilt auch  ${}y\leq _{1}u$.  Aufgrund der Transitivität von ${}\leq _{1}$ gilt  ${}x\leq _{1}u$  und daher

   ${}\varphi (x)\leq _{2}\psi (u)=\varphi (y)\,.$

2. Es seien  ${}x,y\in M_{1}$  mit  ${}\varphi (x)\leq _{2}\varphi (y)$  gegeben. Aus  ${}y\leq _{1}y$  folgt  ${}\varphi (y)\leq _{2}\psi (y)$  und somit haben wir aufgrund der Transitivität von ${}\leq _{2}$ auch  ${}\varphi (x)\leq _{2}\psi (y)$,  was  ${}x\leq y$  bedeutet.
3. Dies folgt unmittelbar aus (1) und (2), da ${}\varphi$ eine bijektive ordnungsvolltreue Abbildung ist.

Aufgabe (1 Punkt)

Es sei ${}G$ der lineare Graph mit ${}7$ Knoten. Skizziere für die möglichen Wurzeln den Graphen ${}G$ derart, dass die Wurzel oben platziert ist und dass der Abstand eines Punktes zur Wurzel direkt über die Höhe der Platzierung erkennbar ist.

Lösung erstellen

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

Es sei ${}G$ ein zusammenhängender Graph mit Durchmesser ${}d$.

1. Zeige, dass es in ${}G$ einen Unterbaum gibt, dessen Durchmesser ebenfalls ${}d$ ist.
2. Zeige, dass in ${}G$ jeder aufspannende Baum einen Durchmesser ${}\geq d$ besitzt.
3. Man gebe ein Beispiel für einen zusammenhängenden Graphen ${}G$ derart, dass jeder aufspannende Baum einen Durchmesser ${}>d$ besitzt.

Lösung

1. Es sei

   $u=v_{0},v_{1},v_{2},\ldots ,v_{d}=v$

   ein verbindender Weg zwischen ${}u$ und ${}v$ ohne (Knoten)-Wiederholung, der den Durchmesser von ${}G$ realisiert. Der entsprechende lineare Graph ist direkt ein Baum mit Durchmesser ${}d$.

2. Beim Übergang zu einem (zusammenhängenden) Untergraphen kann sich der Abstand zwischen zwei Punkten allenfalls erhöhen, da ja Kanten herausgenommen werden. Dies überträgt sich auf den Durchmesser.
3. Wir betrachten den vollständigen Graphen mit ${}3$ Knotenpunkten. Sein Durchmesser ist ${}1$. Die aufspannenden Bäume sind lineare Graphen der Länge ${}2$ mit Durchmesser ${}2$.

Aufgabe (5 (3+2) Punkte)

Es sei ${}G$ ein Graph mit ${}n$ Knotenpunkten.

1. Zeige, dass das charakteristische Polynom die Form

   $x^{n}+c_{n-2}x^{n-2}\ldots$

   besitzt.

2. Zeige, dass die Summe der Eigenwerte der Adjazenzmatrix (mit ihren algebraischen Vielfachheiten gezählt) gleich ${}0$ ist.

Lösung

1. Da die Adjazenzmatrix in der Hauptdiagonalen nur Nullen hat, ist das charakteristische Polynom gleich der Determinante der ${}n\times n$-Matrix

   ${\begin{pmatrix}x&-a_{12}&\ldots &-a_{1n}\\-a_{12}&x&\ddots &-a_{2n}\\\vdots &\ddots &\ddots &\vdots \\-a_{1n}&\ldots &-a_{n-1n}&x\end{pmatrix}},$

   wobei die ${}a_{ij}$ gleich ${}0$ oder gleich ${}1$ sind. Nach dem Entwicklungssatz kommt der Faktor ${}x^{n}$ vor. Die anderen Summanden ergeben sich durch Multipikation von ${}\pm a_{1i}$ mit der Streichungsmatrix. In deren Determinante kommt höchstens die ${}n-2$-te Potenz von ${}x$ vor. Deshalb ist der Koeffizient vor ${}x^{n-1}$ gleich ${}0$.

2. Es sei

   ${}P=\left(x-\lambda _{1}\right)\cdots \left(x-\lambda _{n}\right)\,$

   die Faktorzerlegung des charakteristischen Polynoms, wobei die ${}\lambda _{i}$ die Eigenwerte (mit Wiederholungen) sind. Wenn man dies ausmultipliziert, so ergibt sich

   ${}P=x^{n}+\left(\sum _{i=1}^{n}\lambda _{i}\right)x^{n-1}+\ldots \,.$

   Nach Teil (1) muss also die Summe der Eigenwerte gleich ${}0$ sein.

Aufgabe (1 Punkt)

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

Lösung

Aufgabe (7 Punkte)

Beweise die eulersche Polyederformel.

Lösung

Wir führen Induktion über die Anzahl ${}g$ der Gebiete. Bei  ${}g=1$  liegt ein Baum vor und nach Satz 20.22 (Diskrete Mathematik (Osnabrück 2026)) ist

${}n-m+1=n-(n-1)+1=2\,.$

Es sei die Aussage nun für einen jeden planaren Graphen mit ${}g$ Gebieten bewiesen und sei ${}G$ ein zusammenhängender planarer Graph mit ${}g+1$ Gebieten. Es ist dann ${}G$ kein Baum und besitzt daher einen Zyklus und damit auch einen Kreis, sagen wir  ${}v_{1}\sim v_{2}\sim \ldots \sim v_{r}$.  Bei der Herausnahme der Kante ${}v_{1}v_{2}$ bleibt der Graph zusammenhängend und planar. Die Anzahl der Knoten bleibt gleich, die Anzahl der Kanten reduziert sich um ${}1$ und die beiden durch die Kante ${}v_{1}v_{2}$ begrenzten Gebiete werden zu einem Gebiet vereinigt, die anderen Gebiete ändern sich nicht. Insgesamt reduziert sich also die Anzahl der Gebiete um ${}1$. Da die Anzahl der Kanten und der Gebiete mit unterschiedlichem Vorzeichen in die Wechselsumme eingeht, ändert sich diese bei Herausnahme der Kante nicht. Nach Induktionsvoraussetzung ist die Wechselsumme des reduzierten Graphen gleich ${}2$, deshalb ist die Wechselsumme von ${}G$ ebenfalls gleich ${}2$.