Kurs:Diskrete Mathematik/11/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 3 0 4 0 3 4 0 0 1 0 4 0 0 0 0 0 0 25




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein kommutativer Ring .
  2. Eine Relation auf einer Menge .
  3. Die Folge der euklidischen Reste zu ganzen Zahlen mit .
  4. Die Automorphismengruppe eines ungerichteten Graphen .
  5. Der Umfang eines zyklischen Graphen .
  6. Eine zulässige Färbung eines Graphen .


Lösung

  1. Ein Ring heißt kommutativ, wenn die Multiplikation kommutativ ist.
  2. Eine Relation auf einer Menge ist eine Teilmenge der Produktmenge , also .
  3. Man nennt die durch die Anfangsbedingungen und und die mittels der Division mit Rest

    rekursiv bestimmte Folge die Folge der euklidischen Reste.

  4. Zu einem Graphen nennt man die Gruppe aller Automorphismen

    die Automorphismengruppe von .

  5. Der Umfang eines zyklischen Graphen ist die längste Länge eines Kreises in .
  6. Eine Färbung

    heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Beziehung zwischen der Addition und endlichen Mengen.
  2. Der Satz über die Restklassenkörper von .
  3. Der Rekursionssatz für aufspannende Bäume.


Lösung

  1. Es seien und disjunkte endliche Mengen mit bzw. Elementen. Dann besitzt ihre Vereinigung gerade Elemente.
  2. Es sei . Der Restklassenring ist genau dann ein Körper, wenn eine Primzahl ist.
  3. Es sei ein schleifenfreier Multigraph und eine Kante von . Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang


Aufgabe (3 Punkte)

Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?


Lösung

Das Pickelpaar und die drei übrigen einzelnen Pickel können als vier Pickelfelder betrachtet werden, die in beliebiger Reihenfolge beackert werden könnnen. Dafür gibt es Möglichkeiten. Bei jeder dieser Reihenfolge hat man beim Pickelpaar die freie Wahlmöglichkeit, welcher zuerst drankommt. Daher gibt es insgesamt

Möglichkeiten.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 (1+1+1+1) Punkte)

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

wobei bei der Binomialkoeffizient als zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

  1. Besitzt diese Verknüpfung ein neutrales Element von links?
  2. Besitzt diese Verknüpfung ein neutrales Element von rechts?
  3. Bestimme und .
  4. Ist diese Verknüpfung assoziativ?


Lösung

  1. Es kann kein neutrales Element von links geben, da für gilt
  2. ist das neutrale Element von rechts. Für ist

    und dies gilt auch für .

  3. Es ist

    und

  4. Die Verknüpfung ist nich assoziativ, beispielsweise ist

    aber


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (3 Punkte)

Es sei ein Monoid, und . Zeige die folgenden Potenzgesetze.

  1. Wenn kommutativ ist, so ist


Lösung Monoid/Potenzgesetze/Fakt/Beweis/Aufgabe/Lösung


Aufgabe (4 Punkte)

Es sei eine Menge und eine Ordnung auf . Zeige durch Induktion über die Aussage: Wenn für Elemente die Beziehung

und

gilt, dann sind alle gleich.


Lösung

Der Induktionsanfang folgt unmittelbar aus der Antisymmetrie. Es sei also die Aussage für ein gewisses schon bewiesen und es liegen Elemente mit den Abschätzungen

und

vor. Wegen der Transitivität der Ordnung gilt dann auch

und damit gelten auch die Bedingungen in der Induktionsvoraussetzung. Somit ist also

Wegen

und

stimmt auch mit diesem Element überein.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (1 Punkt)

Finde eine Darstellung der für das Zahlenpaar und .


Lösung

Es ist


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Es sei eine Gruppe. Betrachte die Relation auf , die durch

erklärt ist. Zeige, dass eine Äquivalenzrelation ist.


Lösung

Die Relation ist offenbar reflexiv. Zum Nachweis der Symmetrie sei . Im Fall ist natürlich auch und somit . Im Fall

ergibt sich durch Invertieren der Gleichung

also ebenfalls . Zum Nachweis der Transitivität sei und . Hier gibt es insgesamt vier Fälle. Bei und ist natürlich . Bei und ist , also . Bei und ist , also wieder . Bei und ist

also .


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


Lösung /Aufgabe/Lösung