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.

  1. Eine relationstreue Abbildung , wobei auf und jeweils Relationen fixiert sind.
  2. Die (zugehörige) Ordnung in einem algebraischen Verband .
  3. Stirling-Zahl/2. Art/Partition/Definition/Begriff
  4. Ungerichteter Graph/Homomorphismus/Definition/Begriff
  5. Ungerichteter Graph/Rundgang/Definition/Begriff
  6. Graph/Knotenüberdeckung/Minimal/Definition/Begriff


Lösung

  1. Es seien und Mengen mit darauf erklärten Relationen bzw. . Man nennt eine Abbildung

    relationstreu, wenn für alle mit auch gilt.

  2. In einem algebraischen Verband nennt man die durch

    falls

    definierte Ordnung, die zugehörige Ordnung.

  3. Stirling-Zahl/2. Art/Partition/Definition/Begriff/Inhalt
  4. Ungerichteter Graph/Homomorphismus/Definition/Begriff/Inhalt
  5. Ungerichteter Graph/Rundgang/Definition/Begriff/Inhalt
  6. Graph/Knotenüberdeckung/Minimal/Definition/Begriff/Inhalt


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Die rekursive Beziehung zwischen den Binomialkoeffizienten (Pascalsches Dreieck).
  2. Die Potenzgesetze für ein Monoid.
  3. Der Sechs-Farben-Satz.


Lösung

  1. Die Binomialkoeffizienten erfüllen die rekursive Beziehung
  2. Es sei ein Monoid, und . Dann gelten die folgenden Potenzgesetze.
    1. Wenn kommutativ ist, so ist
  3. 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.


Lösung

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:

  1. Die Fußballweltmeisterschaft findet alle vier Jahre statt.
  2. Deutschland war schon viermal Weltmeister.
  3. Deutschland war zum ersten Mal 1954 und zum letzten Mal 2014 Weltmeister.
  4. 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?


Lösung

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.


Lösung

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)

Es sei eine Menge. Wir betrachten die Verknüpfung

Ist diese Verknüpfung assoziativ?


Lösung

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)

Zeige, dass ein Ring mit der Nullring ist.


Lösung

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.


Lösung

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.


Lösung

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.


Lösung

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.


Lösung

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)


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


Lösung /Aufgabe/Lösung


Aufgabe (8 Punkte)

Beweise den Satz von Ore.


Lösung

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)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung