Kurs:Diskrete Mathematik/18/Klausur

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

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

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

Aufgabe (0 Punkte)

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.

Aufgabe (0 Punkte)

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.

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?

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.

Aufgabe * (1 Punkt)

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

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

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

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.

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 }\,?$

Aufgabe * (5 Punkte)

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

Aufgabe * (4 Punkte)

Beweise den Rekursionssatz für aufspannende Bäume.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

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.