Kurs:Diskrete Mathematik/1/Klausur/kontrolle

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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Aufgabe * (7 Punkte)Referenznummer erstellen

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

Aufgabe * (3 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Skizziere den Teilerfremdheitsgraphen zu den Zahlen

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Bestimme die Automorphismengruppe des abgebildeten Diamantgraphen.

Aufgabe * (4 Punkte)Referenznummer erstellen

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

Aufgabe * (6 Punkte)Referenznummer erstellen

Beweise den Charakterisierungssatz für bipartite Graphen mittels Kreisen.

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

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$.