Kurs:Diskrete Mathematik/9/Klausur


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Punkte 3 3 8 2 1 6 3 5 10 0 1 0 8 8 58




Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Der Binomialkoeffizient .
  2. Ein angeordneter kommutativer Ring .
  3. Ordnungstheorie/Geordnete Menge/Kleinstes Element/Definition/Begriff
  4. Ungerichteter Graph/Vollständig/Definition/Begriff
  5. Ungerichteter Graph/Zusammenhängend/Exzentrizität/Definition/Begriff
  6. Ungerichteter Graph/Inzidenzmatrix/Definition/Begriff



Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Anzahl von bijektiven Abbildungen.
  2. Das Lemma von Euklid.
  3. Der Paarungssatz (Heiratssatz)



Aufgabe * (8 Punkte)

Beweise den Satz über die Addition und endliche Mengen.



Aufgabe * (2 (1+1) Punkte)

Für eine Opernaufführung braucht man für die verschiedenen Rollen eine Altstimme, zwei Sopranstimmen, zwei Tenorstimmen und einen Bass. Im Ensemble stehen zwei Altstimmen, drei Sopranistinnen, vier Tenöre und drei Bässe zur Verfügung.

  1. Wie viele Besetzungsmöglichkeiten für die Rollen gibt es?
  2. Wie viele Möglichkeiten gibt es, die Mitwirkenden auszuwählen, ohne Berücksichtigung der Rolle?



Aufgabe * (1 Punkt)

Zeige, dass zwischen den Binomialkoeffizienten und der Zusammenhang

besteht.



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

Wir betrachten die durch die Wertetabelle

gegebene Abbildung von

in sich selbst.

  1. Erstelle eine Wertetabelle für .
  2. Erstelle eine Wertetabelle für .
  3. Begründe, dass sämtliche iterierten Hintereinanderschaltungen bijektiv sind.
  4. Bestimme für jedes das minimale mit der Eigenschaft, dass

    ist.

  5. Bestimme das minimale mit der Eigenschaft, dass

    für alle ist.



Aufgabe * (3 Punkte)

Es sei eine Menge mit Elementen. Bestimme die Anzahl der Relationen auf , die

  1. reflexiv
  2. symmetrisch
  3. reflexiv und symmetrisch

sind.



Aufgabe * (5 Punkte)

Zeige, dass die Untergruppen von genau die Teilmengen der Form

mit einer eindeutig bestimmten nicht-negativen Zahl sind.



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

Wir betrachten auf die Relation , die durch

festgelegt ist, falls eine Potenz von und eine Potenz von teilt.

  1. Zeige, dass eine Äquivalenzrelation ist.
  2. Bestimme, welche der folgenden Elemente zueinander äquivalent sind, welche nicht.
  3. Es sei die Quotientenmenge zu dieser Äquivalenzrelation und es sei die Menge der Primzahlen mit der Potenzmenge . Zeige, dass es eine natürliche Abbildung

    gibt, die zu einer injektiven Abbildung

    führt. Ist surjektiv?

  4. Wie sieht ein besonders einfaches Repräsentantensystem für die Äquivalenzrelation aus?



Aufgabe (0 Punkte)



Aufgabe (1 Punkt)

Skizziere ein Pfeildiagramm, das die nebenstehende Permutation überschneidungsfrei darstellt.



Aufgabe (0 Punkte)



Aufgabe * (8 Punkte)

Beweise den Satz von Kirchhoff über die Anzahl der Spannbäume.



Aufgabe * weiter

  1. Erstelle einen Nachbarschaftsgraphen zu den Bundesländern.
  2. Bestimme die Blätter.
  3. Was ist der Abstand von Baden-Württemberg zu Niedersachsen?
  4. Was ist der Maximalgrad und in welchem Bundesland wird er angenommen?
  5. Was ist die Exzentrizität von Thüringen?
  6. Ist Deutschland ein Baum?
  7. Ist Deutschland hamiltonsch?
  8. Ist Deutschland hamiltonsch, wenn man die Blätter herausnimmt?
  9. Was ist der Umfang von Deutschland?