Kurs:Diskrete Mathematik/10/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	2	3	3	3	6	6	0	6	0	0	7	0	0	0	0	0	44

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Ein neutrales Element ${}e\in M$ zu einer Verknüpfung
$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.$
Die Symmetrie einer Relation ${}R$ auf einer Menge ${}M$ .
Geordnete Menge/Teilmenge/Untere Schranke/Definition/Begriff
Ungerichteter Graph/Pfad/Definition/Begriff
Ungerichteter Graph/Zyklus/Definition/Begriff
Ungerichter Graph/Paarungszahl/Definition/Begriff

Lösung

Es sei eine Menge ${}M$ mit einer Verknüpfung
$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

gegeben. Dann heißt ein Element ${}e\in M$ neutrales Element der Verknüpfung, wenn für alle ${}x\in M$ die Gleichheit

$x\circ e=x=e\circ x$

gilt.
Die Relation ${}R$ heißt symmetrisch, wenn aus ${}xRy$ stets ${}yRx$ folgt.
Geordnete Menge/Teilmenge/Untere Schranke/Definition/Begriff/Inhalt
Ungerichteter Graph/Pfad/Definition/Begriff/Inhalt
Ungerichteter Graph/Zyklus/Definition/Begriff/Inhalt
Ungerichter Graph/Paarungszahl/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Der Satz über die Wohldefiniertheit der Anzahl.
Das allgemeine Distributivgesetz für einen kommutativen Halbring.
Der Satz von Kirchhoff über die Anzahl der Spannbäume.

Lösung

Wenn ${}M$ eine Menge ist und wenn
$\varphi \colon \{1,\ldots ,n\}\longrightarrow M$

und

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

bijektive Abbildungen sind, so ist

${}n=k\,.$
Es sei ${}R$ ein kommutativer Halbring und es seien ${}a_{1},\ldots ,a_{r},b_{1},\ldots ,b_{s}$ Elemente aus ${}R$ . Dann gilt das allgemeine Distributivgesetz
${}{\left(\sum _{i=1}^{r}a_{i}\right)}{\left(\sum _{k=1}^{s}b_{k}\right)}=\sum _{1\leq i\leq r,\,1\leq k\leq s}a_{i}b_{k}\,.$
Es sei ${}G$ ein Multigraph und sei ${}L$ die Laplace-Matrix zu ${}G$ . Es sei ${}L'$ die Streichungsmatrix von ${}L$ bezüglich eines Knotenpunktes. Dann ist die Anzahl der Spannbäume von ${}G$ gleich der Determinante von ${}L'$ .

Aufgabe (2 Punkte)

Es sei ${}a\in \mathbb {N} _{+}$ . Zeige, wie man ${}a^{10}$ mit vier Multiplikationen berechnen kann.

Lösung

Sei

{}b:=a\cdot a=a^{2}\,

und

{}c:=b\cdot b=b^{2}=a^{4}\,.

Dann ist

{}a^{10}=(c\cdot c)\cdot b\,

eine Berechnung mit vier Multiplikationen.

Aufgabe (2 Punkte)

Gabi Hochster möchte sich die Fingernägel ihrer linken Hand (ohne den Daumennagel) lackieren, wobei die drei Farben ${}B,G,R$ zur Verfügung stehen. Sie möchte nicht, dass zwei benachbarte Finger die gleiche Farbe bekommen. Wie viele Möglichkeiten gibt es?

Lösung

Sie beginnt mit dem Zeigefinger, dafür hat sie drei Möglichkeiten. Für den Mittelfinger hat sie zwei Möglichkeiten, da die Farbe des Zeigefingers ausgeschlossen ist. Für den Ringfinger hat sie wieder zwei Möglichkeiten, da die Farbe des Mittelfingers ausgeschlossen ist. Für die Farbe des kleinen Fingers hat sie wieder zwei Möglichkeiten, da die Farbe des Ringfingers ausgeschlossen ist. Insgesamt gibt es also

{}3\cdot 2\cdot 2\cdot 2=24\,

Möglichkeiten.

Aufgabe (3 Punkte)

Zeige, dass die Binomialkoeffizienten die rekursive Beziehung

{}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,

erfüllen.

Lösung

Es ist

{}{\begin{aligned}{\binom {n}{k}}+{\binom {n}{k-1}}&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n-(k-1))!(k-1)!}}\\&={\frac {n!}{(n-k)!k!}}+{\frac {n!}{(n+1-k)!(k-1)!}}\\&={\frac {(n+1-k)\cdot n!}{(n+1-k)!k!}}+{\frac {k\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1-k+k)\cdot n!}{(n+1-k)!k!}}\\&={\frac {(n+1)!}{(n+1-k)!k!}}\\&={\binom {n+1}{k}}.\end{aligned}}

Aufgabe (3 Punkte)

Es sei ${}G$ eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der Potenzmenge ${}{\mathfrak {P}}\,(G)$ .

Lösung

Die Menge sei ${}M=\{a,b\}$ , die Potenzmenge ist dann

{}{\mathfrak {P}}\,(M)=\{\emptyset ,\{a\},\{b\},\{a,b\}\}\,.

Die Verknüpfungstabelle für die Vereinigung ist

${}\cup$	${}\emptyset$	${}\{a\}$	${}\{b\}$	${}\{a,b\}$
${}\emptyset$	${}\emptyset$	${}\{a\}$	${}\{b\}$	${}\{a,b\}$
${}\{a\}$	${}\{a\}$	${}\{a\}$	${}\{a,b\}$	${}\{a,b\}$
${}\{b\}$	${}\{b\}$	${}\{a,b\}$	${}\{b\}$	${}\{a,b\}$
${}\{a,b\}$	${}\{a,b\}$	${}\{a,b\}$	${}\{a,b\}$	${}\{a,b\}$

Aufgabe (3 Punkte)

Beweise das folgende Untergruppenkriterium. Eine nichtleere Teilmenge ${}H\subseteq G$ einer Gruppe ${}G$ ist genau dann eine Untergruppe, wenn gilt:

{\text{ für alle }}g,h\in H{\text{ ist }}gh^{-1}\in H.

Lösung Untergruppenkriterium/Aufgabe/Lösung

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

Zu ${}n\in \mathbb {N}$ sei

{}[n]=\{0,1,2,\ldots ,n\}\,.

Zu jedem ${}n\in \mathbb {N}$ und jedem ${}0\leq k\leq n$ seien die Abbildungen

D_{k}\colon [n]\longrightarrow [n+1]

durch

{}D_{k}(j)={\begin{cases}j,{\text{ falls }}j<k,\\j+1{\text{ sonst}},\end{cases}}\,

und die Abbildungen

S_{k}\colon [n+1]\longrightarrow [n]

durch

{}S_{k}(j)={\begin{cases}j,{\text{ falls }}j\leq k,\\j-1{\text{ sonst}},\end{cases}}\,

definiert.

a) Erstelle eine Wertetabelle für

D_{3}\colon [4]\longrightarrow [5].

b) Erstelle eine Wertetabelle für

S_{3}\colon [6]\longrightarrow [5].

c) Beschreibe die durch die Wertetabelle

${}j$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$
${}\varphi (j)$	${}0$	${}2$	${}2$	${}4$	${}5$	${}5$

gegebene Abbildung

\varphi \colon [5]\longrightarrow [5]

als eine Hintereinanderschaltung von geeigneten ${}D_{k}$ und ${}S_{i}$ .

Lösung

a)

${}j$	${}0$	${}1$	${}2$	${}3$	${}4$
${}D_{3}(j)$	${}0$	${}1$	${}2$	${}4$	${}5$

b)

${}j$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}S_{3}(j)$	${}0$	${}1$	${}2$	${}3$	${}3$	${}4$	${}5$

c) Wir behaupten

{}\varphi =D_{3}\circ D_{1}\circ S_{3}\circ S_{1}\,.

Die Komposition hat für die Elemente ${}0,1,2,3,4,5$ jeweils den folgenden Effekt:

0\mapsto 0\mapsto 0\mapsto 0\mapsto 0,

1\mapsto 1\mapsto 1\mapsto 2\mapsto 2,

2\mapsto 1\mapsto 1\mapsto 2\mapsto 2,

3\mapsto 2\mapsto 2\mapsto 3\mapsto 4,

4\mapsto 3\mapsto 3\mapsto 4\mapsto 5,

5\mapsto 4\mapsto 3\mapsto 4\mapsto 5.

Das Gesamtergebnis stimmt also mit ${}\varphi$ überein.

Aufgabe (6 Punkte)

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen ${}a$ und ${}b$ durch Induktion über das Maximum von ${}a$ und ${}b$ .

Lösung

Wir beweisen die Aussage durch Induktion über das Maximum von ${}a$ und ${}b$ , wobei wir ohne Einschränkung ${}a\leq b$ wählen können. Wenn das Maximum ${}0$ ist, so sind beide Zahlen ${}0$ und somit nicht teilerfremd. Wenn das Maximum ${}1$ ist, so ist ${}b=1$ und somit ergeben ${}r=0$ und ${}s=1$ eine Darstellung der ${}1$ . Es seien nun ${}a\leq b$ teilerfremd, ${}b\geq 2$ und die Aussage sei für alle Zahlenpaare, deren Maxima kleiner als ${}b$ sind, schon bewiesen. Dann ist ${}a<b$ , da bei ${}a=b$ die beiden Zahlen nicht teilerfremd sind. Ebenso können wir ${}a=0$ ausschließen. Wir betrachten das Zahlenpaar ${}(a,b-a)$ und wollen darauf die Induktionsvoraussetzung anwenden. Das Maximum dieses neuen Paares ist jedenfalls kleiner als ${}b$ . Allerdings müssen wir, damit die Induktionsvoraussetzung wirklich angewendet werden kann, wissen, dass auch ${}a$ und ${}b-a$ teilerfemd sind. Dazu führen wir einen Widerspruchsbeweis. Nehmen wir also an, dass ${}a$ und ${}b-a$ nicht teilerfremd sind. Dann gibt es eine natürliche Zahl ${}t\geq 2$ , die sowohl ${}a$ als auch ${}b-a$ teilt. Dies bedeutet wiederum, dass es natürliche Zahlen ${}m,n$ mit ${}a=mt$ und ${}b-a=nt$ gibt. Doch dann ist

{}b=(b-a)+a=nt+mt=(n+m)t\,

ebenfalls ein Vielfaches von ${}t$ , im Widerspruch zur Teilerfremdheit von ${}a$ und ${}b$ . Die Induktionsvoraussetzung ist also auf ${}a$ und ${}b-a$ anwendbar und somit gibt es ganze Zahlen ${}r,s$ mit

{}ra+s(b-a)=1\,.

Dann ist aber auch

{}(r-s)a+sb=ra+s(b-a)=1\,

und wir haben eine Darstellung der ${}1$ mit ${}a$ und ${}b$ gefunden.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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

Es sei ${}M$ die Menge der zweimal stetig differenzierbaren Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$ . Definiere auf ${}M$ eine Relation durch

f\sim g{\text{ falls }}f(0)=g(0),\,f'(0)=g'(0){\text{ und }}f^{\prime \prime }(1)=g^{\prime \prime }(1).

a) Zeige, dass dies eine Äquivalenzrelation ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

Lösung

a) Wir betrachten die Abbildung

H\colon M\longrightarrow \mathbb {R} ^{3},\,f\longmapsto (f(0),f'(0),f^{\prime \prime }(1)).

Zwei Funktionen ${}f$ und ${}g$ stehen genau dann in dieser Relation zueinander, wenn ihre Bilder unter ${}H$ übereinstimmen. Daher liegt eine Äquivalenzrelation vor (und ${}H$ beschreibt die Äquivalenzklassenbildung).

b) Das Polynom

a+bx+{\frac {c}{2}}x^{2}

wird unter ${}H$ auf ${}(a,b,c)$ abgebildet, sodass dieses Polynom diese Klasse repräsentiert.

c) Es sei ${}f_{1}\sim g_{1}$ und ${}f_{2}\sim g_{2}$ . Es ist ${}(f_{1}+f_{2})\sim (g_{1}+g_{2})$ zu zeigen. Dies folgt aber sofort aufgrund der Additivität der Ableitung.

d) Wir betrachten ${}f_{1}=g_{1}=x$ und ${}f_{2}=x$ und ${}g_{2}=x^{3}-3x^{2}+x$ . Offenbar ist ${}f_{1}\sim g_{1}$ . Die relevanten Werte für ${}f_{2}$ sind wegen ${}f_{2}=x,\,f_{2}'=1,\,f_{2}^{\prime \prime }=0$ einfach

H(f_{2})=(0,1,0).

Für ${}g_{2}$ ergibt sich ${}g_{2}=x^{3}-3x^{2}+x,\,g_{2}'=3x^{2}-6x+1,\,g_{2}^{\prime \prime }=6x-6$ . Daher ist

H(g_{2})=(0,1,0),

sodass ${}f_{2}\sim g_{2}$ ist. Wir behaupten, dass ${}f_{1}f_{2}$ und ${}g_{1}g_{2}$ nicht äquivalent sind. Es ist ${}f_{1}f_{2}=x^{2}$ mit den Ableitungen ${}(x^{2},2x,2)$ und daher ist

H(f_{1}f_{2})=(0,0,2).

Für ${}g_{1}g_{2}=x(x^{3}-3x^{2}+x)=x^{4}-3x^{3}+x^{2}$ hat man die Ableitungen ${}(x^{4}-3x^{3}+x^{2},4x^{3}-9x^{2}+2x,12x^{2}-18x+2)$ und daher ist

H(g_{1}g_{2})=(0,0,-4)\neq H(f_{1}f_{2}).

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (7 Punkte)

Beweise den Charakterisierungssatz für Bäume.

Lösung

Aus (1) folgt (2). Da ${}G$ nach Voraussetzung zusammenhängend ist, gibt es zu ${}u,v$ zumindest einen verbindenden Weg. Würde es zwei Wege geben, so könnte man daraus direkt einen Zyklus und dann auch einen Kreis konstruieren, was ausgeschlossen ist.

Aus (2) folgt (1). Die Zusammenhangseigenschaft ist klar. Würde es einen Kreis geben, so könnte man dies direkt als einen zweifachen Weg ohne Wiederholung zwischen zwei Punkten auffassen.

Aus (1) folgt (3). Wir führen Induktion über die Anzahl der Punkte von ${}G$ . Bei einem einzigen Punkt gibt es keine Kante und die Gleichung stimmt. Es sei also ${}G$ ein Baum mit ${}n\geq 2$ Punkten. Nach Lemma 17.20 (Diskrete Mathematik (Osnabrück 2020)) besitzt ${}G$ ein Blatt und nach Lemma 17.21 (Diskrete Mathematik (Osnabrück 2020)) ist ${}G\setminus b$ ebenfalls ein Baum. Dabei wird ein Punkt und eine Kante herausgenommen. Nach Induktionsvoraussetzung gilt die Gleichung für den verkleinerten Baum, also gilt sie auch für ${}G$ .

Von (3) nach (1). Wir führen wieder Induktion über die Knotenanzahl, bei einem Knoten ist alles klar. Aufgrund der Voraussetzung und Lemma 15.16 (Diskrete Mathematik (Osnabrück 2020)) gilt

{}\sum _{v\in V}d(v)=2\cdot {\left({\#\left(V\right)}-1\right)}=2{\#\left(V\right)}-2\,.

Wegen der Zusammenhangseigenschaft sind die Grade zumindest ${}1$ . Deshalb muss es (zumindest ${}2$ ) Punkte mit Grad ${}1$ , also Blätter geben. Es sei ${}b$ ein Blatt. Die Formel gilt dann auch für ${}G\setminus b$ . Nach Induktionsvoraussetzung ist ${}G\setminus b$ ein Baum, und daher ist nach Lemma 17.21 (Diskrete Mathematik (Osnabrück 2020)) auch ${}G$ ein Baum.