Kurs:Diskrete Mathematik/18/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	0	2	0	3	6	3	1	6	7	5	4	0	0	0	0	2	45

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Relation/Linkseindeutig/Definition/Begriff
2. Verband/Boolesch/Definition/Begriff
3. Eine Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Ungerichteter Graph/Automorphismengruppe/Homogen/Definition/Begriff
5. Ungerichteter Graph/Aufspannender Wald/Definition/Begriff
6. Ungerichter Graph/Knotenteilmenge/Paarung/Definition/Begriff

Lösung

1. Relation/Linkseindeutig/Definition/Begriff/Inhalt
2. Verband/Boolesch/Definition/Begriff/Inhalt
3. Eine Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$ ist eine Relation, die die folgenden drei Eigenschaften besitzt (für beliebige ${}x,y,z\in M$).
   1. ${}x\sim x$.
   2. Aus ${}x\sim y$ folgt ${}y\sim x$.
   3. Aus ${}x\sim y$ und ${}y\sim z$ folgt ${}x\sim z$.
4. Ungerichteter Graph/Automorphismengruppe/Homogen/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Aufspannender Wald/Definition/Begriff/Inhalt
6. Ungerichter Graph/Knotenteilmenge/Paarung/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 (1+1) Punkte)

Anna-Lena, Marie-Simone, Hans-Peter und Fritz-Franz gehen zur Farbberatung. Es ergibt sich folgende Empfehlung. Anna-Lena stehen die Farben grün, gelb und pink, Marie-Simone steht gelb und feuerrot, Hans-Peter steht grün, grau und graublau, Fritz-Franz stehen alle bisher genannten Farben außer graublau, dafür zusätzlich noch violett. Es sei ${}P$ die Menge der vier Personen und ${}F$ die Menge der erwähnten Farben zuzüglich blau.

1. Erstelle eine Tabelle und ein Verbindungsdiagramm, die die Relation aus Personen und Farben wiedergibt.
2. Bestimme die Fasern zu blau, zu grün und zu Marie-Simone.

Lösung

1. 	grün	gelb	pink	feuerrot	grau	graublau	violett	blau
   Anna-Lena	${}{\text{x}}$	${}{\text{x}}$	${}{\text{x}}$	${}-$	${}-$	${}-$	${}-$	${}-$
   Marie-Simone	${}-$	${}{\text{x}}$	${}-$	${}{\text{x}}$	${}-$	${}-$	${}-$	${}-$
   Hans-Peter	${}{\text{x}}$	${}-$	${}-$	${}-$	${}{\text{x}}$	${}{\text{x}}$	${}-$	${}-$
   Fritz-Franz	${}{\text{x}}$	${}{\text{x}}$	${}{\text{x}}$	${}{\text{x}}$	${}{\text{x}}$	${}-$	${}{\text{x}}$	${}-$

2. Die Faser zu blau ist leer, die Faser zu grün ist ${}\{{\text{Anna-Lena}},{\text{Hans-Peter}},{\text{Fritz-Franz}}\}$ und die Faser zu Marie-Simone ist ${}\{{\text{gelb}},{\text{feuerrot}}\}$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (3 Punkte)

Für ein doppelverpacktes Geschenk soll eine würfelförmige Schachtel in eine etwas größere würfelförmige Schachtel hineingelegt werden. Bestimme auf unterschiedliche Arten, wie viele Möglichkeiten es dafür gibt.

Lösung

Wir denken uns den größeren Würfel fest.

Es gibt ${}6$ Möglichkeiten, auf dem kleineren Würfel eine Seite auszusuchen, die der Boden sein soll. Wenn dies festgelegt ist, so gibt es noch ${}4$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind ${}24$ Möglichkeiten.

Es gibt ${}8$ Möglichkeiten, auf dem kleineren Würfel eine Ecke auszusuchen, die mit einer fixierten Ecke der größeren Würfelschachtel deckungsgleich werden soll. Wenn dies festgelegt ist, so gibt es noch ${}3$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind ${}24$ Möglichkeiten

Es gibt ${}12$ Möglichkeiten, auf dem kleineren Würfel eine Kante auszusuchen, die mit einer fixierten Kante der größeren Würfelschachtel deckungsgleich werden soll. Wenn dies festgelegt ist, so gibt es noch ${}2$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind ${}24$ Möglichkeiten

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

Eine ${}n$-Schokolade ist ein rechteckiges Raster, das durch ${}a-1$ Längsrillen und ${}b-1$ Querrillen in ${}n=a\cdot b$ (${}a,b\in \mathbb {N} _{+}$) mundgerechte kleinere Stücke eingeteilt ist. Ein Teilungsschritt an einer Schokolade ist das vollständige Durchtrennen einer Schokolade längs einer Längs- oder Querrille. Eine vollständige Aufteilung einer Schokolade ist eine Folge von Teilungsschritten (an der Ausgangsschokolade oder an einer zuvor erhaltenen Zwischenschokolade), deren Endprodukt aus den einzelnen Stücken besteht. Bei einer gegebenen vollständigen Aufteilung ${}A$ einer Schokolade kann man sich für jedes Stück ${}s$ fragen, wie oft es bei einem Teilungsschritt der Aufteilung beteiligt war. Diese Zahl nennen wir die Aufteilungstiefe von ${}s$. Die Summe aller Aufteilungstiefen zu allen Stücken nennen wir die Gesamtaufteilungstiefe der Aufteilung.

1. Es sei eine ${}4\times 4$-Schokolade gegeben. Zeige, dass es eine vollständig Aufteilung gibt, bei der jedes Stück die Aufspaltungstiefe ${}4$ besitzt.
2. Wir betrachten ein Eckstück einer ${}4\times 4$-Schokolade. Was ist seine minimale Aufteilungstiefe und was ist seine maximale Aufteilungstiefe?
3. Hängt für eine fixierte Schokolade die Gesamtaufteilungstiefe von der Aufteilung ab?

Lösung

1. Man halbiert zuerst in der Mitte, die beiden ${}2\times 4$-Schokoladen halbiert man so, dass jeweils ${}2\times 2$-Schokoladen entstehen, diese halbiert man wieder und die entstehenden ${}2\times 1$-Schokoladen halbiert man noch mal. Bei diesem Aufteilungsprozess ist jedes Stück an ${}4$ Teilungen beteiligt. Die Aufspaltungstiefe ist also ${}4$ für jedes Stück.
2. Die minimale Aufteilungstiefe eines Eckstückes ist ${}2$, diese erreicht man, indem man von der Gesamtschokolade eine Einerreihe mit der Ecke abtrennt und daraus dann die Ecke als Einzelstück abtrennt. Aufteilungstiefe ${}1$ ist sicher nicht möglich. Die maximale Aufteilungstiefe ist ${}6$. Größer kann sie nicht sein, da es nur drei Quer- und drei Längsrillen gibt und die Anzahl der Rillen auf den Teilschokoladen bei jedem Teilungsschritt um zumindest ${}1$ kleiner wird. Unter der Aufteilung, bei der man stets eine die Ecke nicht enthaltende Einerrandreihe abtrennt, besitzt die Ecke die Aufteilungstiefe ${}6$.
3. Die Gesamtaufteilungstiefe hängt von der Aufteilung ab. Betrachten wir eine ${}4\times 1$-Schokolade. Wenn man in der Mitte halbiert und dann noch die beiden Teilschokoladen albiert, so ist jedes Stück an zwei Teilungsvorgängen beteiligt, die Gesamtaufteilungstiefe ist also ${}8$. Wenn man hingegen jeweils ein Randstück abtrennt, so ist die Summe der Aufteilungstiefen gleich

   ${}1+2+3+3=9\,.$

Aufgabe (3 (2+1) Punkte)

Es seien ${}a,b$ positive natürliche Zahlen. Die Summe der Stammbrüche ist dann

${}{\frac {1}{a}}+{\frac {1}{b}}={\frac {b+a}{ab}}\,.$

a) Zeige, dass bei ${}a,b$ teilerfremd diese Darstellung gekürzt ist.

b) Zeige, dass im Allgemeinen diese Darstellung nicht gekürzt sein muss.

Lösung

a) Es seien ${}a$ und ${}b$ teilerfremd und es sei ${}p$ eine Primzahl. Wenn ${}p$ den Nenner ${}ab$ teilt, so teilt es nach dem Lemma von Euklid einen der Faktoren, sagen wir ${}a$. Dann teilt es wegen der Teilerfremdheit nicht auch ${}b$. Somit teilt es auch nicht ${}a+b$ und Zähler und Nenner sind teilerfremd.

b) Sei

${}a=b=2\,.$

Dann ist

${}{\frac {1}{2}}+{\frac {1}{2}}={\frac {2+2}{2\cdot 2}}={\frac {4}{4}}\,$

und dies ist keine teilerfremde Darstellung.

Aufgabe (1 Punkt)

Es sei ${}G$ eine Gruppe. Zeige, dass

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

für alle ${}x\in G$ ist.

Lösung

Es ist

${}x\circ x^{-1}=1\,.$

Damit ist ${}x$ das Inverse zu ${}x^{-1}$. Damit ist

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

Aufgabe (6 Punkte)

Zeige, dass es zu ganzen Zahlen ${}d,n$ mit ${}d>0$ eindeutig bestimmte ganze Zahlen ${}q,r$ mit ${}0\leq r<d$ und mit

${}n=dq+r\,$

gibt.

Lösung

Zur Existenz. Bei ${}n=0$ ist ${}q=r=0$ eine Lösung. Es sei ${}n$ positiv. Da ${}d$ positiv ist, gibt es ein Vielfaches ${}ad\geq n$. Daher gibt es auch eine Zahl ${}q$ mit $qd\leq n$ und $(q+1)d>n$. Es sei ${}r:=n-qd$. Dann ist

${}qd\leq qd+r<qd+d\,$

und daher ist ${}0\leq r<d$ wie gewünscht. Bei ${}n$ negativ kann man schreiben ${}-n={\tilde {q}}d+{\tilde {r}}$ nach dem Resultat für positive Zahlen. Daraus ergibt sich

$n=(-{\tilde {q}})d-{\tilde {r}}={\begin{cases}(-{\tilde {q}})d+0{\text{ bei }}{\tilde {r}}=0\\(-{\tilde {q}}-1)d+d-{\tilde {r}}{\text{ sonst}}\,.\end{cases}}$

Im zweiten Fall erfüllen ${}q=-{\tilde {q}}-1$ und ${}r=d-{\tilde {r}}$ die Bedingungen.
Zur Eindeutigkeit. Es sei ${}qd+r=n={\tilde {q}}d+{\tilde {r}}$, wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung ${}{\tilde {r}}\geq r$. Dann gilt ${}(q-{\tilde {q}})d={\tilde {r}}-r$. Diese Differenz ist nichtnegativ und kleiner als ${}d$, links steht aber ein Vielfaches von ${}d$, sodass die Differenz ${}0$ sein muss und die beiden Darstellungen überein stimmen.

Aufgabe weiter

Es sei ${}M$ die Menge der Mäuse und ${}L$ die Menge der Löcher auf einem Feld. Es wird beobachtet, dass jede Maus gewisse Löcher benutzt, andere dagegen vermeidet. Zu einer Teilmenge an Löchern ${}S\subseteq L$ definieren wir

${}S^{\perp }={\left\{m\in M\mid m{\text{ benutzt alle Löcher aus }}S\right\}}\,,$

und zu einer Teilmenge an Mäusen ${}T\subseteq M$ definieren wir

${}T^{\perp }={\left\{\ell \in L\mid \ell {\text{ wird von jeder Maus aus }}T{\text{ benutzt}}\right\}}\,.$

1. Beschreibe zu einem Loch ${}\ell \in L$ die Menge ${}\{\ell \}^{\perp }$ mit einem Satz.
2. Beschreibe die Menge ${}L^{\perp }$ mit einem Satz.
3. Beschreibe die Menge ${}M^{\perp }$ mit einem Satz.
4. Zeige: Zu Teilmengen ${}S_{1}\subseteq S_{2}$ (in ${}L$) ist

   ${}{\left(S_{1}\right)}^{\perp }\supseteq {\left(S_{2}\right)}^{\perp }\,.$

5. Zeige: Für eine beliebige Teilmenge ${}S\subseteq L$ ist

   ${}S\subseteq {\left(S^{\perp }\right)}^{\perp }\,.$

6. Zeige: Für eine Vereinigung

   ${}S=S_{1}\cup S_{2}\subseteq L\,$

   ist

   ${}{\left(S_{1}\cup S_{2}\right)}^{\perp }={\left(S_{1}\right)}^{\perp }\cap {\left(S_{2}\right)}^{\perp }\,.$

7. Gilt für einen Durchschnitt

   ${}S=S_{1}\cap S_{2}\subseteq L\,.$

   die Beziehung

   ${}{\left(S_{1}\cap S_{2}\right)}^{\perp }={\left(S_{1}\right)}^{\perp }\cup {\left(S_{2}\right)}^{\perp }\,?$

8. Gilt für eine beliebige Teilmenge ${}S\subseteq L$ die Beziehung

   ${}S^{\perp }={\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }\,?$

Lösung

1. Das ist die Menge aller Mäuse, die dieses Loch benutzen.
2. Das ist die Menge derjenigen Mäuse, die jedes Loch benutzen.
3. Das ist die Menge derjenigen Löcher, die von allen Mäusen benutzt werden.
4. Es sei ${}m\in {\left(S_{2}\right)}^{\perp }$. Dies bedeutet, dass ${}m$ alle Löcher aus ${}S_{2}$ benutzt. Dann benutzt ${}m$ erst recht alle Löcher aus der Teilmenge ${}S_{1}$, also gilt ${}m\in {\left(S_{1}\right)}^{\perp }$.
5. Es sei ${}\ell \in S$. Die Menge ${}S^{\perp }$ besteht aus allen Mäusen, die alle Löcher aus ${}S$ benutzen. Diese Mäusemenge benutzt insbesondere ${}\ell$, daher ist ${}\ell \in {\left(S^{\perp }\right)}^{\perp }$.
6. Wegen ${}S_{1}\subseteq S_{1}\cup S_{2}$ gilt nach Teil (4)

   ${}{\left(S_{1}\cup S_{2}\right)}^{\perp }=S_{1}^{\perp }\,$

   und entsprechend für ${}S_{2}$. Dies ergibt die Inklusion ${}{\left(S_{1}\cup S_{2}\right)}^{\perp }\subseteq S_{1}^{\perp }\cap S_{1}^{\perp }$. Es sei nun ${}m=S_{1}^{\perp }\cap S_{1}^{\perp }$. Dies bedeutet, dass ${}m$ alle Löcher aus ${}S_{1}$ und alle Löcher aus ${}S_{2}$ benutzt. Also benutzt ${}m$ alle Löcher aus ${}S_{1}\cup S_{2}$, also ${}m\in {\left(S_{1}\cup S_{2}\right)}^{\perp }$.

7. Dies muss nicht gelten. Es kann beispielsweise ${}L$ disjunkt zerlegt in ${}S_{1}$ und ${}S_{2}$ sein. Dann ist ${}S_{1}\cap S_{2}=\emptyset$ und ${}\emptyset ^{\perp }=M$. Es kann aber gleichzeitig sein, dass es sowohl in ${}S_{1}$ als auch in ${}S_{2}$ jeweils ein Loch gibt, das von keiner Mausbenutzt wird. Dann ist

   ${}{\left(S_{1}\right)}^{\perp }=\emptyset ={\left(S_{2}\right)}^{\perp }\,.$

8. Das gilt. Nach (4) ist ${}S\subseteq {\left(S^{\perp }\right)}^{\perp }$, woraus mit (5) die Inklusion

   ${}{\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }\subseteq S^{\perp }\,.$

   Die zu (4) analoge Eingenschaft gilt auch für Teilmengen ${}T\subseteq M$. Angewendet auf ${}T=S^{\perp }$, ergibt sich

   ${}S^{\perp }\subseteq {\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }\,.$

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 (4 Punkte)

Beweise den Rekursionssatz für aufspannende Bäume.

Lösung

Sei ${}e=\{u,v\}$. Ein Spannbaum in ${}G$ enthält entweder diese Kante oder nicht. Wir zeigen, dass es im ersten Fall eine Bijektion zu den Spannbäumen der Kontraktion ${}G/(e)$ und im zweiten Fall eine Bijektion zu den Spannbäumen von ${}G\setminus \{e\}$ gibt. Dies ist im zweiten Fall unmittelbar klar. Betrachten wir also die Spannbäume in ${}G$, in denen ${}e$ vorkommt. Wenn man diese Kante herausnimmt, so erhält man einen Spannbaum von ${}G/(e)$, da ja die Endpunkte von ${}e$ miteinander identifiziert werden. Es sei umgekehrt ein Spannbaum von ${}G/(e)$ gegeben. Dieser durchläuft jeden Punkt von ${}G/(e)$, also auch den Kontraktionspunkt ${}[u]=[v]$. Indem man die Kante ${}e$ an dieser Stelle einbaut, erhält man einen Spannbaum von ${}G$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (2 Punkte)

Es sollen drei Häuser jeweils mit Leitungen an Wasser, Gas und Elektrizität angeschlossen werden. Beschreibe eine Möglichkeit, bei der es nur eine Überschneidung gibt.

Lösung Wasser/Gas/Elektrizität/Eine Überschneidung/Aufgabe/Lösung