Kurs:Diskrete Mathematik/22/Klausur
| Aufgabe | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Punkte | 3 | 3 | 4 | 6 | 2 | 2 | 2 | 3 | 1 | 3 | 3 | 2 | 6 | 6 | 3 | 5 | 4 | 1 | 5 | 64 |
Aufgabe * (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Ein gemeinsamer Teiler von natürlichen Zahlen .
- Ein Infimum zu einer Teilmenge in einer geordneten Menge .
- Ein Verband .
- Der Kantengraph zu einem Graphen .
- Ein Weg in einem Graphen.
- Ein planarer Graph.
Aufgabe * (3 Punkte)
Formuliere die folgenden Sätze.
- Der Satz über die Restklassenkörper von .
- Der Satz über die Anzahl der Abbildungen mit vorgeschriebener Faseranzahl.
- Der Satz über nichtgeschlossene Eulerzüge.
Aufgabe * (4 (2+1+1) Punkte)
Folgende Aussagen seien bekannt.
- Der frühe Vogel fängt den Wurm.
- Doro wird nicht von Lilly gefangen.
- Lilly ist ein Vogel oder ein Igel.
- Für Igel ist 5 Uhr am Morgen spät.
- Doro ist ein Wurm.
- Für Vögel ist 5 Uhr am Morgen früh.
- Lilly schläft bis 5 Uhr am Morgen und ist ab 5 Uhr unterwegs.
Beantworte folgende Fragen.
- Ist Lilly ein Vogel oder ein Igel?
- Ist sie ein frühes oder ein spätes Tier?
- Fängt der späte Igel den Wurm?
Aufgabe * (6 (1+5) Punkte)
Es seien natürliche Zahlen. Zu bezeichnet die Menge der Permutationen auf und bezeichnet die Menge der -elementigen Teilmengen von .
- Zeige
- Man definiere eine explizite natürliche bijektive Abbildung
Aufgabe * (2 Punkte)
Zeige, dass in einem kommutativen Halbring die Beziehung gilt.
Aufgabe * (2 Punkte)
Berechne
Aufgabe * (2 Punkte)
Bestimme, ob die durch die Relationstabelle
beschriebene Relation auf der Menge reflexiv, symmetrisch, transitiv, antisymmetrisch ist.
Aufgabe * (3 Punkte)
Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .
Aufgabe * (1 Punkt)
Finde die Primfaktorzerlegung von
Aufgabe * (3 Punkte)
Es sei ein Körper und ein Untervektorraum. Wir betrachten die Relation auf dem , die durch
definiert ist. Zeige, dass diese Relation eine Äquivalenzrelation ist.
Aufgabe * (3 Punkte)
Es sei eine Gruppe. Zeige, dass sich Gruppenelemente und Gruppenhomomorphismen von nach über die Korrespondenz
entsprechen.
Aufgabe * (2 Punkte)
Zeige, dass es keinen Ringhomomorphismus von nach gibt.
Aufgabe * (6 Punkte)
Zeige, dass zwei Permutationen auf bzw. genau dann zueinander konjugiert sind, wenn ihre Zyklendarstellung den gleichen Typ haben, d.h. wenn die Anzahl der Zyklen und deren Längen übereinstimmen.
Aufgabe (6 (2+2+2) Punkte)
Es sei eine Matrixrekursion über einem endlichen Körper zur -Matrix .
- Zeige, dass die Lösungsfolge zu jedem Startvektor letztlich periodisch ist.
- Zeige, dass bei die Lösungsfolge von Anfang an periodisch ist.
- Zeige, dass bei die Lösungsfolge nicht von Anfang an periodisch sein muss.
Aufgabe * (3 Punkte)
Bestimme die erzeugende Funktion zur Folge der Quadratzahlen , .
Aufgabe * (5 (1+1+1+2) Punkte)
Es seien ein endlicher kommutativer Ring und es sei der Nullteilergraph von . Zu betrachten wir die Multiplikationsabbildung
- Zeige, dass einen schwachen Graphhomomorphismus von nach induziert.
- Man gebe ein Beispiel, dass keinen (echten) Graphhomomorphismus induziert.
- Zeige, dass genau dann eine Einheit in ist, wenn einen Graphautomorphismus bewirkt.
- Man gebe ein Beispiel für einen endlichen kommutativen Ring und einen Graphautomorphismus des Nullteilergraphen, der nicht von der Multiplikation mit einem Element herrührt.
Aufgabe * (4 Punkte)
Es sei der Graph auf der Knotenmenge mit der einzigen Kante . Bestimme die Adjazenzmatrix zu sowie das charakteristische Polynom, die Eigenwerte mit Vielfachheiten und die Eigenräume zu .
Aufgabe (1 Punkt)
Begründe, dass der abgebildete Graph hamiltonsch ist.
Aufgabe * (5 Punkte)
Es sei ein Graph, es sei eine Kante von mit dem zugehörigen Kontraktionsgraphen . Zeige, dass das chromatische Polynom die Gleichung
erfüllt.
