Kurs:Diskrete Mathematik/1/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Potenzmenge zu einer Menge ${}M$.
2. Ein minimales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Ein Repräsentantensystem zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Der Maximalgrad eines Graphen ${}G=(V,E)$.
5. Ein Wald.
6. Die Knotenüberdeckungszahl eines Graphen ${}G=(V,E)$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Die Siebformel.
2. Der Isomorphiesatz für endliche boolesche Verbände.
3. Der Satz von König für einen bipartiten Graphen.

Aufgabe * (2 Punkte)

Vor einem Fußballspiel begrüßt jeder der elf Spieler einer Mannschaft jeden Spieler der anderen Mannschaft, jeder Spieler begrüßt die vier Unparteiischen und diese begrüßen sich alle untereinander. Wie viele Begrüßungen finden statt?

Aufgabe * (5 (1+3+1) Punkte)

Zu je zwei Punkten in der Produktmenge ${}\mathbb {Q} ^{2}$ gibt es eine Verbindungsgerade und einen Mittelpunkt, der die Verbindungsstrecke halbiert.

1. Man gebe zu zwei Punkten ${}(a_{1},a_{2})$ und ${}(b_{1},b_{2})$ die Koordinaten des Mittelpunktes an.
2. Es seien in der Produktmenge ${}\mathbb {Z} ^{2}$ fünf Punkte gegeben (jeder Punkt habe also ganzzahlige Koordinaten). Zeige, dass mindestens einer der Mittelpunkte ganzzahlige Koordinaten haben muss.
3. Gilt die Eigenschaft aus (2) auch bei vier Punkten?

Aufgabe * (5 Punkte)

Beweise den binomischen Lehrsatz für einen kommutativen Halbring ${}R$.

Aufgabe * (2 Punkte)

Es sei ${}M=\{a,b\}$ eine zweielementige Menge. Beschreibe vollständig (durch Auflistung aller zugehörigen Paare) die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch die Teilmengenbeziehung gegeben ist.

Aufgabe * (2 (1+0.5+0.5) Punkte)

Wir betrachten das Spiel Schnick Schnack Schnuck mit den Objekten Schere, Stein, Papier und Brunnen als eine Gewinnrelation.

1. Skizziere diese Gewinnrelation durch einen gerichteten Graphen (Pfeildiagramm).
2. Ist die Gewinnrelation transitiv?
3. Gibt es eine dreielementige Teilmenge der Objekte derart, dass die darauf eingeschränkte Relation transitiv ist?

Aufgabe (0 Punkte)

Aufgabe * (7 Punkte)

Beweise den Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.

Aufgabe * (3 Punkte)

Zeige, dass auf der Funktionenmenge ${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ Infima und Suprema existieren und dass somit ${}M$ ein Verband ist. Skizziere das Infimum von der Sinusfunktion und der Kosinusfunktion.

Aufgabe * (6 (2+2+2) Punkte)

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Relation auf ${}M$, die reflexiv und transitiv sei.

1. Zeige, dass auf ${}M$ durch ${}x\sim y$, falls ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ ist, eine Äquivalenzrelation definiert wird.
2. Es sei ${}Q$ die Quotientenmenge zu ${}M$ zur Äquivalenzrelation aus (1). Zeige, dass durch ${}[x]\leq [y]$, falls ${}x\preccurlyeq y$, eine wohldefinierte Relation auf ${}Q$ gegeben ist.
3. Zeige, dass die Relation auf ${}Q$ aus (2) eine Ordnungsrelation ist.

Aufgabe * (2 Punkte)

Skizziere den Teilerfremdheitsgraphen zu den Zahlen

$1,2,3,4,6,8,9,12.$

Aufgabe * (3 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Diamantgraphen.

Aufgabe * (4 Punkte)

Bestimme die Anzahl der Spannbäume des vollständigen Graphen zu ${}4$ Punkten mit Hilfe des Satzes von Kirchhoff.

Aufgabe * (6 Punkte)

Beweise den Charakterisierungssatz für bipartite Graphen mittels Kreisen.

Aufgabe * (9 (1+1+2+5) Punkte)

Wir betrachten Graphen

${}G=S(n_{1},n_{2},\ldots ,n_{k})\,$

von der folgenden Bauart: Es gibt ein Zentrum ${}z$, an das ${}k$ lineare Graphen (Strahlen) der Länge ${}n_{1},n_{2},\ldots ,n_{k}$ anliegen. Ansonsten gibt es keine weiteren Kanten.

1. Skizziere einen solchen Graphen für ${}k=5$ und

   ${}(n_{1},n_{2},n_{3},n_{4},n_{5})=(2,3,1,3,4)\,.$

2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von ${}G$.
3. Beschreibe eine minimale Knotenüberdeckung von ${}G$, die ${}z$ enthält, und eine minimale Knotenüberdeckung, die ${}z$ nicht enthält.
4. Bestimme die Knotenüberdeckungszahl von ${}G$.