Kurs:Diskrete Mathematik/14/Klausur mit Lösungen
Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Punkte | 3 | 3 | 5 | 3 | 4 | 1 | 2 | 4 | 2 | 4 | 2 | 0 | 0 | 0 | 0 | 0 | 8 | 0 | 0 | 41 |
Aufgabe (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Eine relationstreue Abbildung , wobei auf und jeweils Relationen fixiert sind.
- Die (zugehörige) Ordnung in einem algebraischen Verband .
- Stirling-Zahl/2. Art/Partition/Definition/Begriff
- Ungerichteter Graph/Homomorphismus/Definition/Begriff
- Ungerichteter Graph/Rundgang/Definition/Begriff
- Graph/Knotenüberdeckung/Minimal/Definition/Begriff
- Es seien
und
Mengen mit darauf erklärten
Relationen
bzw. .
Man nennt eine Abbildung
relationstreu, wenn für alle mit auch gilt.
- In einem
algebraischen Verband
nennt man die durch
falls
definierte Ordnung, die zugehörige Ordnung.
- Stirling-Zahl/2. Art/Partition/Definition/Begriff/Inhalt
- Ungerichteter Graph/Homomorphismus/Definition/Begriff/Inhalt
- Ungerichteter Graph/Rundgang/Definition/Begriff/Inhalt
- Graph/Knotenüberdeckung/Minimal/Definition/Begriff/Inhalt
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
- Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
- Die Potenzgesetze für ein Monoid.
- Der Sechs-Farben-Satz.
- Die Binomialkoeffizienten erfüllen die rekursive Beziehung
- Es sei ein
Monoid,
und
.
Dann gelten die folgenden Potenzgesetze.
- Wenn kommutativ ist, so ist
- Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens sechs Farben.
Aufgabe (5 (3+2) Punkte)
Es seien und nichtleere Mengen und
Abbildungen für . Es sei , , und die Produktabbildung, also
a) Zeige, dass genau dann surjektiv ist, wenn alle surjektiv sind.
b) Zeige, dass a) nicht gelten muss, wenn die beteiligten Mengen leer sein dürfen.
a) Es seien alle surjektiv und sei . Zu jedem gibt es ein mit . Daher ist ein Urbild von unter .
Es sei umgekehrt surjektiv, und sei gegeben. Da die alle nicht leer sind, gibt es jeweils ein . Wir setzen
Dafür gibt es nach Voraussetzung ein Urbild . Für die -te Komponente davon muss gelten.
b) Es sei , sei die leere Abbildung und seien und irgendwelche (nichtleere) Mengen und sei eine beliebige nicht surjektive Abbildung. Dann ist und und daher ist die Produktabbildung ebenfalls die leere Abbildung, also surjektiv, obwohl nicht alle surjektiv sind.
Aufgabe (3 Punkte)
Petra hat folgende Informationen über die Erfolge von Deutschland bei Fußballweltmeisterschaften:
- Die Fußballweltmeisterschaft findet alle vier Jahre statt.
- Deutschland war schon viermal Weltmeister.
- Deutschland war zum ersten Mal 1954 und zum letzten Mal 2014 Weltmeister.
- Deutschland war nie zweimal hintereinander Weltmeister.
Wie viele Möglichkeiten für die Jahre, in denen Deutschland die zweite bzw. die dritte Weltmeisterschaft gewann, verbleiben?
Die zweite und die dritte Weltmeisterschaft muss zwischen 1962 und 2006 (einschließlich) gewonnen worden sein. In diesem Zeitraum fanden 12 Weltmeisterschaften statt. Daher gibt es in diesem Zeitraum Jahrespaare, in denen die Gewinne stattgefunden haben können. Da Petra weiß, dass Deutschland nie direkt hintereinander gewonnen hat, muss sie die aufeinanderfolgenden Paare abziehen. Davon gibt es 11. Also verbleiben insgesamt Möglichkeiten.
Aufgabe (4 Punkte)
Beweise durch Induktion, dass für die Abschätzung
gilt.
Induktionsanfang für . Es ist
Zum Induktionsschluss sei . Dann ist
Andererseits ist nach der binomischen Formel
Wir müssen
nachweisen. Der erste Summand stimmt links und rechts überein, für die anderen Summanden zeigen wir, dass die linken, also jeweils , mindestens so groß wie die rechten sind. Dies folgt aber direkt aus (da ), aus , da ja ist, aus und aus .
Aufgabe (1 Punkt)
Diese Verknüpfung ist nicht assoziativ. Um dies zu zeigen, kann man einfach
nehmen, wobei eine nichtleere Menge sei. Dann ist und somit ist einerseits
und andererseits
Aufgabe (2 Punkte)
Es sei ein Ring mit und sei ein Ringelement. Dann gilt nach Eigenschaften der Multiplikation
Also ist jedes Element gleich und der Ring ist der Nullring.
Aufgabe (4 Punkte)
Zeige durch Induktion, dass jede nichtleere Teilmenge ein kleinstes Element besitzt.
Wir betrachten die Aussage
- = Alle Teilmengen von , die enthalten, besitzen ein Minimum.
Da jede nichtleere Teilmenge mindestens ein
besitzt, ist die Aussage des Satzes äquivalent zur Gültigkeit von für alle . Diese Aussage können wir durch Induktion beweisen. Die Aussage besagt, dass jede Teilmenge
,
die die enthält, auch ein Minimum enthält. Dies ist aber klar, da dann eben das Minimum ist. Es sei die Aussage nun für alle
schon bewiesen. Wir müssen beweisen. Es sei also
eine Teilmenge, die enthält.
Wenn auch eine Zahl
besitzt, so besitzt nach der Induktionsvoraussetzung ein Minimum. Andernfalls besitzt keine Zahl, die kleiner als ist. Dann ist aber das Minimum von .
Aufgabe (2 Punkte)
Beweise die Formel
mit Hilfe des allgemeinen binomischen Lehrsatzes.
Der binomische Lehrsatz besagt
Wir setzen . Dann ergibt sich auf der linken Seite
und auf der rechten Seite einfach .
Aufgabe (4 Punkte)
Beweise die Eindeutigkeit der Primfaktorzerlegung für natürliche Zahlen.
Die Eindeutigkeit wird durch Induktion über gezeigt. Für liegt eine Primzahl vor. Es sei nun und seien zwei Zerlegungen in Primfaktoren gegeben, sagen wir
Wir müssen zeigen, dass nach Umordnung die Primfaktorzerlegungen übereinstimmen. Die Gleichheit bedeutet insbesondere, dass die Primzahl das Produkt rechts teilt. Nach dem Lemma von Euklid muss dann einen der Faktoren rechts teilen. Nach Umordnung können wir annehmen, dass von geteilt wird. Da selbst eine Primzahl ist, folgt, dass sein muss. Daraus ergibt sich durch Kürzen, dass
ist. Nennen wir diese Zahl . Da ist, können wir die Induktionsvoraussetzung auf anwenden und erhalten, dass links und rechts die gleichen Primzahlen stehen.
Aufgabe (2 Punkte)
Seien und Mengen und sei eine Abbildung. Zeige, dass durch die Festlegung
wenn
eine Äquivalenzrelation auf definiert wird.
Da der Funktionswert eindeutig bestimmt und die Gleichheit reflexiv ist, gilt offenbar . Wenn ist, so bedeutet das und wegen der Symmetrie der Gleichheit folgt , was wiederum bedeutet. Wenn und ist, so bedeutet dies einerseits und andererseits . Wegen der Transitivität der Gleichheit folgt , was bedeutet.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (8 Punkte)
Beweise den Satz von Ore.
Wir argumentieren bei einer fixierten Knotenmenge absteigend über die Kantenmenge. Für einen vollständigen Graphen ist die Aussage richtig. Wir müssen zeigen, dass die Aussage richtig bleibt, wenn man aus einem Graphen, für den die Aussage gilt, eine Kante herausnimmt. Es sei also ein Graph, für den es einen Hamiltonkreis gibt, und es sei die Kante, die wir herausnehmen. Es sei der verkleinerte Graph. Wenn es in einen Hamiltonkreis gibt, in dem nicht vorkommt, so ist dies direkt ein Hamiltonkreis für . Es sei also (alle beziehen sich auf )
mit ein Hamiltonkreis von . Wir betrachten die Mengen
und
Dabei ist (in der Definition von ) als zu interpretieren und die Nachbarschaften beziehen sich auf . Aufgrund der Voraussetzung über die Grade ( und sind nicht adjazent und ist so groß wie ) ist
Das Element gehört nicht zur Vereinigung , da ein Knotenpunkt nicht mit sich selbst benachbart ist. Daher gibt es nach der Siebformel ein Element
Es gibt also die Verbindungskanten und und somit den Hamiltonkreis
der ohne die Kante auskommt und daher ein Hamiltonkreis in ist.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)