Kurs:Diskrete Mathematik/2/Klausur mit Lösungen/kontrolle

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

Aufgabe (3 Punkte)

Lösung

1. Ein Monoid ist eine Menge ${}M$ zusammen mit einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M$

   und einem ausgezeichneten Element ${}e\in M$ derart, dass folgende beiden Bedingungen erfüllt sind.

   1. Die Verknüpfung ist assoziativ, d.h. es gilt

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

      für alle ${}x,y,z\in M$.

   2. ${}e$ ist neutrales Element der Verknüpfung, d.h. es gilt

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

      für alle ${}x\in M$.

2. Eine natürliche Zahl ${}g$ heißt größter gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}g$ ein gemeinsamer Teiler der ${}a_{i}$ ist und wenn jeder gemeinsame Teiler ${}t$ der ${}a_{i}$ dieses ${}g$ teilt
3. Die Äquivalenzrelation ${}\sim _{H}$ ist auf ${}G$ durch ${}x\sim _{H}y$, falls ${}x-y\in H$, definiert.
4. Ein Graphisomorphismus ist ein Graphhomomorphismus ${}\varphi \colon G\rightarrow H$, wenn es einen Graphhomomorphismus

   $\psi \colon H\longrightarrow G$

   derart gibt, dass

   ${}\psi \circ \varphi =\operatorname {Id} _{V}\,$

   und

   ${}\varphi \circ \psi =\operatorname {Id} _{W}\,$

   gilt.

5. Der vollständige bipartite Graph ${}K_{m,n}$ ist derjenige Graph, dessen Knotenmenge aus der disjunkten Vereinigung einer ${}m$-elementigen Menge ${}A$ und einer ${}n$-elementigen Menge ${}B$ besteht und dessen Kantenmenge durch

   ${}E={\left\{\{a,b\}\mid a\in A,\,b\in B\right\}}\,$

   gegeben ist.

6. Die Paarungsbedingung ist erfüllt, wenn für jede Teilmenge ${}S\subseteq A$ die Beziehung ${}{\#\left(S\right)}\leq {\#\left(N(S)\right)}$ gilt.

Aufgabe (3 Punkte)

Lösung

1. Es seien ${}L$ und ${}M$ endliche Mengen und es sei

   $f\colon L\longrightarrow M$

   eine Abbildung. Dann gilt

   ${}{\#\left(L\right)}=\sum _{y\in M}{\#\left(f^{-1}(y)\right)}\,.$

2. Jede natürliche Zahl ${}n\in \mathbb {N}$, ${}n\geq 2$, besitzt eine eindeutige Zerlegung in Primfaktoren.
3. Es sei ${}G=(V,E)$ ein Graph mit nichtleerer Knotenmenge ${}V$. Dann sind folgende Aussagen äquivalent.
   1. ${}G$ ist ein Baum.
   2. Zwischen je zwei Punkten ${}u,v\in V$ gibt es einen eindeutigen Verbindungsweg ohne Wiederholung.
   3. ${}G$ ist zusammenhängend und es gilt ${}{\#\left(E\right)}={\#\left(V\right)}-1$.

Aufgabe (2 Punkte)

Zwei Personen wollen ihre Körpergröße vergleichen. Sie können sich direkt vergleichen, indem sie sich Rücken an Rücken hinstellen, oder, indem sie ein Maßband (Zollstock) nehmen und ihre Größe damit jeweils messen. Welche Analogien zu diesen Methoden gibt es, wenn man zwei endliche Mengen vergleichen möchte?

Lösung

Es seien ${}M$ und ${}N$ die beiden beteiligten endlichen Mengen.

Direkter Vergleich: Man bestimmt, ob es eine injektive Abbildung von ${}M$ nach ${}N$ gibt (und umgekehrt), ob also die eine Menge in der anderen Menge „Platz“ hat.

Indirekter Vergleich mit Hilfe eines neutralen Vergleichsmaßstabes: Man zählt die beiden Mengen mit Hilfe der natürlichen Zahlen ab und vergleicht dann die dabei ermittelten Anzahlen.

Aufgabe (2 Punkte)

Es findet das olympische 100-Meter-Finale mit acht Teilnehmern statt. Sie wissen, welche drei Teilnehmer eine Medaille gewinnen (aber nicht, wer welche Medaille gewinnt). Wie viele Möglichkeiten für das Gesamtergebnis aller acht Teilnehmer verbleiben (keine Platzierung ist doppelt besetzt)?

Lösung

Für die drei Medaillengewinner, die man kennt, gibt es ${}3!=6$ Möglichkeiten, und für die fünf weiteren Plätze gibt es ${}5!=120$ Möglichkeiten. Insgesamt gibt es also

${}6\cdot 120=720\,$

Möglichkeiten.

Aufgabe (4 (2+2) Punkte)

Es sei ${}S=\{0,1\}$. Betrachte das Monoid ${}M$, das aus allen Abbildungen von ${}S$ nach ${}S$ besteht mit der Hintereinanderschaltung ${}\circ$ von Abbildungen als Verknüpfung.

1. Beschreibe die Elemente in ${}M$ und erstelle eine Verknüpfungstabelle für ${}M$.
2. Bestimme sämtliche Untermonoide von ${}M$ und entscheide jeweils, ob sie kommutativ sind und ob es sich um Gruppen handelt.

Lösung

(1). Es gibt vier Abbildungen der zweielementigen Menge in sich selbst, nämlich die Identität ${}I$, die Vertauschung ${}V$, die durch ${}V(0)=1{\text{ und }}V(1)=0$ festgelegt ist, und die beiden konstanten Abbildungen, die wir mit ${}0$ bzw. ${}1$ bezeichnen. Die Verknüpfungstabelle, bei der im Kreuzungspunkt von der ${}\varphi$-Zeile mit der ${}\psi$-Spalte die Verknüpfung ${}\varphi \circ \psi$ (also ${}\psi$ zuerst angewendet) steht, sieht folgendermaßen aus:

${}\circ$	${}I$	${}V$	${}0$	${}1$
${}I$	${}I$	${}V$	${}0$	${}1$
${}V$	${}V$	${}I$	${}1$	${}0$
${}0$	${}0$	${}0$	${}0$	${}0$
${}1$	${}1$	${}1$	${}1$	${}1$

(2). Die Identität ${}I$ ist das neutrale Element des Monoids, jedes Untermonoid muss dieses Element enthalten.

Das kleinste Untermonoid ist ${}\{I\}$, das ist eine kommutative Gruppe.

${}\{I,V\}$ ist ebenfalls eine kommutative Gruppe, da ${}V$ zu sich selbst invers ist.

${}\{I,0\}$ ist ein kommutatives Untermonoid, wegen ${}I\circ 0=0=0\circ I$ und ${}0\circ 0=0$, aber keine Gruppe, da es kein inverses Element zu ${}0$ gibt.

${}\{I,1\}$ ist ebenfalls ein kommutatives Untermonoid und keine Gruppe (gleicher Grund).

${}\{I,0,1\}$ ist ein Untermonoid, da es unter der Operation abgeschlossen ist. Es ist keine Gruppe, da ${}0$ und ${}1$ nicht invertierbar sind. Es ist nicht kommutativ, da ${}0\circ 1=0$ und ${}1\circ 0=1$ ist.

Wenn man zu ${}\{I,V\}$ noch ein Element dazu tut, so ist wegen ${}V\circ 0=1$ auch das andere drin. Daher gibt es nur noch das volle Untermonoid ${}\{I,V,0,1\}$, das weder kommutativ noch eine Gruppe ist.

Aufgabe (3 Punkte)

Beweise die Nichtnullteilereigenschaft für einen Körper ${}K$.

Lösung

 Nehmen wir an, dass ${}a$ und ${}b$ beide von ${}0$ verschieden sind. Dann gibt es dazu inverse Elemente ${}a^{-1}$ und ${}b^{-1}$ und daher ist ${}(ab){\left(b^{-1}a^{-1}\right)}=1$. Andererseits ist aber nach Voraussetzung ${}ab=0$ und daher ist nach Lemma 5.11 (Diskrete Mathematik (Osnabrück 2020))  (1)

${}(ab){\left(b^{-1}a^{-1}\right)}=0{\left(b^{-1}a^{-1}\right)}=0\,,$

 sodass sich der Widerspruch

${}0=1$ ergibt.

Aufgabe (4 Punkte)

Es sei ${}M$ eine Menge und ${}P$ die Potenzmenge von ${}M$. Betrachte die Relation ${}T$ auf ${}P$, die durch

$T(A,B){\text{ genau dann, wenn }}A\subseteq B$

gegeben ist (dabei sind also ${}A$ und ${}B$ Teilmengen von ${}M$). Bestimme die Anzahl der Elemente dieser Relation, wenn ${}M$ ${}n$ Elemente besitzt.

Lösung

Die Anzahl der Paare ${}(A,B)$, die zu dieser Relation gehören (also ${}A\subseteq B$ erfüllen), ist ${}3^{n}$. Für jedes ${}x\in M$ gibt es nämlich die drei Möglichkeiten

$x\notin A,x\notin B,$

$x\notin A,x\in B,$

$x\in A,x\in B$

(${}x\in A,x\notin B$ ist wegen der Inklusionsbeziehung nicht möglich). Das Paar ${}(A,B)$ ist eindeutig bestimmt, wenn man für jedes ${}x\in M$ weiß, welcher der drei Fälle vorliegt. Für verschiedene Elemente haben diese Fälle nichts miteinander zu tun, daher muss man die jeweiligen ${}3$ Möglichkeiten miteinander multiplizieren, das ergibt ${}3^{n}$.

Aufgabe (1 Punkt)

Skizziere den Graphen der Addition

$+\colon \mathbb {R} \times \mathbb {R} \longrightarrow \mathbb {R} ,\,(x,y)\longmapsto x+y.$

Lösung Graph (Abbildung)/R/Addition/Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sei ${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ die Menge aller Abbildungen von ${}\mathbb {R}$ nach ${}\mathbb {R}$. Wir definieren auf ${}M$ die Relation

${}f\preccurlyeq g\,,$

falls es ein ${}a\in \mathbb {R}$ derart gibt, dass

${}f(x)\leq g(x)\,$

für alle ${}x\geq a$ gilt. Welche Eigenschaften einer Ordnungsrelation sind erfüllt, welche nicht?

Lösung

Die Relation ist reflexiv, da man jedes ${}a$ nehmen kann. Die Relation ist auch transitiv: Die Voraussetzungen ${}f\preccurlyeq g$ und ${}g\preccurlyeq h$ bedeuten, dass es reelle Zahlen ${}a,b\in \mathbb {R}$ derart gibt, dass ${}f(x)\leq g(x)$ für alle ${}x\geq a$ und ${}g(x)\leq h(x)$ für alle ${}x\geq b$ gilt. Dann gilt für alle ${}x\geq {\max {\left(a,b\right)}}$ auch ${}f(x)\leq h(x)$. Die Antisymmetrie gilt nicht. Wenn ${}f$ die Nullfunktion ist und ${}g$ eine beliebige Funktion, die auf ${}\mathbb {R} _{\geq 0}$ die Nullfunktion ist, im negativen Bereich aber nicht, so gilt nach Definition ${}f\preccurlyeq g$ und ebenso ${}g\preccurlyeq f$, die Funktionen sind aber nicht gleich.

Aufgabe (3 Punkte)

Zeige, dass in einem (ordnungstheoretischen) Verband ${}V$ das Absorptionsgesetz

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

für alle ${}x,y\in V$ gilt.

Lösung

Es ist direkt

${}x\leq x\sqcup (x\sqcap y)\,.$

Ferner ist

${}x\sqcap y\leq x\,$

und somit ist ${}x$ eine obere Schranke von ${}x$ und von ${}x\sqcap y$ und daher ist

${}x\sqcup (x\sqcap y)\leq x\,.$

Aus der Antisymmetrie folgt

${}x=x\sqcup (x\sqcap y)\,.$

Aufgabe (4 Punkte)

Beweise das Kernkriterium für die Injektivität eines Gruppenhomomorphismus

$\varphi \colon G\longrightarrow H.$

Lösung

Wenn ${}\varphi$ injektiv ist, so darf auf jedes Element ${}h\in H$ höchstens ein Element aus ${}G$ gehen. Da ${}e_{G}$ auf ${}e_{H}$ geschickt wird, darf kein weiteres Element auf ${}e_{H}$ gehen, d.h. ${}\ker \varphi =\{e_{G}\}$. Es sei umgekehrt dies der Fall und sei angenommen, dass ${}g,{\tilde {g}}\in G$ beide auf ${}h\in H$ geschickt werden. Dann ist

${}\varphi {\left(g{\tilde {g}}^{-1}\right)}=\varphi (g)\varphi ({\tilde {g}})^{-1}=hh^{-1}=e_{H}\,$

und damit ist ${}g{\tilde {g}}^{-1}\in \ker \varphi$, also ${}g{\tilde {g}}^{-1}=e_{G}$ nach Voraussetzung und damit ${}g={\tilde {g}}$.

Aufgabe (3 Punkte)

Man bestimme den größten gemeinsamen Teiler von ${}3146$ und ${}1515$ und man gebe eine Darstellung des ${}\operatorname {ggT}$ von ${}3146$ und ${}1515$ mittels dieser Zahlen an.

Lösung

Der euklidische Algorithmus liefert:

$3146=2\cdot 1515+116$

$1515=13\cdot 116+7$

$116=16\cdot 7+4$

$7=1\cdot 4+3$

$4=1\cdot 3+1.$

Die Zahlen ${}3146$ und ${}1515$ sind also teilerfremd und ${}1$ ist ihr größter gemeinsamer Teiler. Eine Darstellung der ${}1$ erhält man, indem man diese Division mit Rest rückwärts liest, also

${}{\begin{aligned}1&=4-1\cdot 3\\&=4-(7-1\cdot 4)\\&=2\cdot 4-7\\&=2(116-16\cdot 7)-7\\&=2\cdot 116-33\cdot 7\\&=2\cdot 116-33(1515-13\cdot 116)\\&=-33\cdot 1515+(2+13\cdot 33)\cdot 116\\&=-33\cdot 1515+431\cdot 116\\&=-33\cdot 1515+431(3146-2\cdot 1515)\\&=-895\cdot 1515+431\cdot 3146.\end{aligned}}$

Aufgabe (5 Punkte)

Es sei ${}R$ ein kommutativer Halbring und seien ${}x_{1},\ldots ,x_{k}\in R$ Elemente und ${}n\in \mathbb {N}$. Zeige

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

Lösung

Bei einem Produkt von Summen in einem kommutativen Halbring muss jeder Summand mit jedem Summanden multipliziert werden. Betrachten wir also

${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}={\left(x_{1}+\cdots +x_{k}\right)}\cdot {\left(x_{1}+\cdots +x_{k}\right)}\cdots {\left(x_{1}+\cdots +x_{k}\right)}\,$

mit ${}n$ Faktoren. In jedem Faktor wird jeweils ein Summand ${}x_{i}$ ausgewählt, dies ergibt stets ein Produkt der Form ${}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}$ mit

${}r_{1}+\cdots +r_{k}=n\,.$

Dabei ist ${}r_{j}$ die Anzahl, wie oft ${}x_{j}$ ausgewählt wurde. Somit ist die Gesamtpotenz eine Summe mit den Summanden ${}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}$, und wir müssen uns fragen, wie viele Möglichkeiten es gibt, ${}n$-fach aus der Menge ${}\{1,2,\ldots ,k\}$ Elemente zu ziehen, derart, dass die Zahl ${}j$ genau ${}r_{j}$-fach gezogen wird. Die Anzahl dieser Möglichkeiten wird aber durch die Multinomialkoeffizienten ${}{\binom {n}{r_{1},\dotsc ,r_{k}}}$ beschrieben.

Aufgabe (1 Punkt)

Lege in der Skizze für die drei Häuser überschneidungsfrei Wege zu den zugehörigen gleichfarbigen Gartentoren an.

Lösung Häuser/Gartentor/Verbindung/Aufgabe/Lösung

Aufgabe weiter

Wir betrachten den folgenden Graphen. Die Knotenmenge besteht aus den Zahlen von ${}10$ bis ${}99$, und zwei Zahlen werden genau dann durch eine Kante verbunden, wenn sie in genau einer Ziffer (an der richtigen Stelle) übereinstimmen.

1. Bestimme den Grad zu jedem Punkt des Graphen.
2. Wie viele Knoten und wie viele Kanten besitzt der Graph?
3. Was ist der Durchmesser des Graphen?
4. Was ist der Radius des Graphen?
5. Gibt es einen Graphautomorphismus, der die ${}21$ in die ${}12$ überführt und die ${}23$ auf sich selbst?
6. Ist die Vertauschung von Einer- und Zehnerziffer ein Graphautomorphismus?

Lösung

1. Für jeden Knotenpunkt ${}(a,b)$ kann man die benachbarten Punkte aufzählen: Man kann die vordere Ziffer gleich lassen und die hintere abändern, wofür es ${}9$ Möglichkeiten gibt, oder man kann die hintere Ziffer gleich lassen und die vordere abändern, wofür es ${}8$ Möglichkeiten gibt (die ${}0$ fehlt). Der Grad ist also stets ${}17$.
2. Der Graph besitzt ${}90$ Knotenpunkte und somit ${}45\cdot 17=765$ Kanten.
3. Der Durchmesser ist ${}2$, da jedenfalls je zwei Knotenpunkte höchstens den Abstand ${}2$ haben, da man ja höchstens die beiden Ziffern abändern muss. Da es zu jeder zweistelligen Zahl auch eine weitere zweistellige Zahl gibt, die in beiden Ziffern verschieden sind, ist der Durchmesser genau ${}2$.
4. Mit dem gleichen Argument ist der Radius ${}2$.
5. ${}21$ und ${}23$ sind durch eine Kante verbunden, ${}12$ und ${}23$ aber nicht, es gibt also keinen solchen Graphautomorphismus.
6. Nein, da ja ${}10$ gar nicht auf ${}01$ abgebildet werden kann, da dies nicht zur Menge gehört.

Aufgabe (1 Punkt)

Bestimme die Adjazenzmatrix zum abgebildeten Graphen.

Lösung

Die Adjazenzmatrix ist

${\begin{pmatrix}0&1&1&1\\1&0&1&0\\1&1&0&1\\1&0&1&0\end{pmatrix}}.$

Aufgabe (5 Punkte)

Beweise den Satz über den Zusammenhang von Graphen mit Blättern.

Lösung

Es sei ${}G$ zusammenhängend und ${}u,v\in G\setminus \{b\}$. Dann gibt es in ${}G$ einen verbindenden Weg von ${}u$ nach ${}v$. Wenn in diesem Weg ${}b$ vorkommt, so jedenfalls nicht als Anfangs- oder als Endpunkt, da dies explizit ausgeschlossen ist. Wenn ${}b$ in der Mitte vorkommt, so in der Form ${}w,b,w$, wobei ${}\{b,w\}$ die einzige Kante an ${}b$ bezeichne. Doch in diesem Fall kann man diesen Wegabschnitt herausnehmen und erhält einen kürzeren Weg von ${}u$ nach ${}v$. Deshalb gibt es auch einen verbindenen Weg, wo ${}b$ gar nicht vorkommt.

Es sei nun ${}G\setminus \{b\}$ zusammenhängend und seien ${}u,v\in G$. Wenn ${}u,v\neq b$ ist, so kann man direkt einen verbindenden Weg aus ${}G\setminus \{b\}$ nehmen. Wenn ${}u=b$ ist, so ist ${}b$ mit einem weiteren Knotenpunkt ${}w$ verbunden, und einen Weg in ${}G\setminus \{b\}$ von ${}w$ nach ${}v$ kann man durch die Kante ${}\{b,w\}$ zu einem Weg in ${}G$ von ${}b$ nach ${}v$ fortsetzverlämgern.

Aufgabe (2 Punkte)

Es sei ${}G$ ein Graph und ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus in einen bipartiten Graphen ${}H$. Zeige, dass ${}G$ ebenfalls bipartit ist.

Lösung

Es sei ${}H=A\uplus B$ eine bipartite Zerlegung von ${}H$. Dann ist ${}G=\varphi ^{-1}(A)\uplus \varphi ^{-1}(B)$ eine Zerlegung. Diese ist auch bipartit. Würde es nämlich in ${}G$ eine Kante ${}\{x,y\}$ mit ${}x,y\in \varphi ^{-1}(A)$ geben, so würde es direkt auch die Kante ${}\{\varphi (x),\varphi (y)\}$ innerhalb von ${}A$ in ${}H$ geben, ein Widerspruch.

Aufgabe (2 Punkte)

Zeige, dass man im Satz von Berge nicht darauf verzichten kann, dass die Endpunkte der alternierenden Wege verschieden sind.

Lösung

Wir betrachten einen Rundgang mit drei Punkten. Eine Paarung mit einer einzigen Kante ist bereits maximal und optimal. Den Rundgang selbst kann man als einen alternierenden Weg auffassen, der in dem von der einzigen Paarungskante unabgedeckten Punkt startet und endet.

Aufgabe (2 Punkte)

Ist es möglich, die Karte der deutschen Bundesländer mit drei Farben zulässig einzufärben?

Lösung

Das ist nicht möglich. An Thüringen grenzen ${}5$ Länder an, die untereinander einen Kreis bilden, Bayern, Sachsen, Sachsen-Anhalt, Niedersachsen, Hessen. Dieser Kreis braucht jedenfalls drei Farben für eine zulässige Färbung, Thüringen braucht also eine vierte Farbe.

Aufgabe (4 Punkte)

Zeige durch Induktion über ${}n$, dass das chromatische Polynom eines Rundganges mit ${}n$ Knoten gleich ${}(X-1)^{n}+(-1)^{n}(X-1)$ ist.

Lösung

Für ${}n=3$ ist das chromatische Polynom nach Beispiel 24.8 (Diskrete Mathematik (Osnabrück 2020)) gleich

${}X(X-1)(X-2)=(X-1)(X^{2}-2X)=(X-1)((X-1)^{2}-1)=(X-1)^{3}-(X-1)\,,$

was den Induktionsanfang sichert. Es sei nun ${}G$ ein Rundgang mit ${}n\geq 4$ und sei die Aussage für kleinere Rundgänge bereits bekannt. Wir verwenden Lemma 24.12 (Diskrete Mathematik (Osnabrück 2020))  (1) mit einer beliebigen Kante. Hierbei ist ${}G\setminus \{e\}$ ein linearer Graph mit ${}n$ Knoten und ${}G/e$ ist ein Rundgang mit ${}n-1$ Knoten, auf den wir die Induktionsvoraussetzung anwenden können. Somit ist unter Verwendung von Aufgabe 24.11 (Diskrete Mathematik (Osnabrück 2020)) das chromatische Polynom des Rundganges mit ${}n$ Knoten gleich

${}{\begin{aligned}X(X-1)^{n-1}-{\left((X-1)^{n-1}+(-1)^{n-1}(X-1)\right)}&=X(X-1)^{n-1}-(X-1)^{n-1}+(-1)^{n}(X-1)\\&={\left(X-1\right)}(X-1)^{n-1}+(-1)^{n}(X-1)\\&=(X-1)^{n}+(-1)^{n}(X-1).\end{aligned}}$