Kurs:Diskrete Mathematik/22/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 | 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.
- Eine natürliche Zahl heißt gemeinsamer Teiler der , wenn jedes teilt für .
- Ein Element heißt Infimum von , wenn die größte untere Schranke von ist.
- Ein Verband ist eine geordnete Menge mit der Eigenschaft, dass für je zwei Elemente ein Infimum und ein Supremum existieren.
- Der Kantengraph ist derjenige Graph, dessen Knotenmenge die Kantenmenge von ist und bei dem zwei Knoten und (also Kanten aus ) genau dann durch eine Kante verbunden werden, wenn und einen gemeinsamen Punkt in besitzen.
- Ein Weg ist eine Folge von Knoten derart, dass für alle eine Kante ist.
- Ein Graph heißt planar, wenn er eine geometrische Realisierung im besitzt.
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.
- Es sei . Der Restklassenring ist genau dann ein Körper, wenn eine Primzahl ist.
- Es sei eine -elementige Menge und seien mit
vorgegeben.
Dann ist die Anzahl der Abbildungen von nach mit der Eigenschaft, dass
für alle ist, gleich
- In einem zusammenhängenden Graphen gibt es genau dann einen nichtgeschlossenen Eulerzug, wenn es genau zwei Knotenpunkte mit ungeradem Grad gibt.
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?
- Lilly ist ein Igel. Beweis durch Widerspruch. Nehmen wir an, dass Lilly kein Igel ist. Dann ist sie nach (3) ein Vogel. Da Lilly nach (7) um Uhr schon unterwegs ist, ist nach (6) Lilly ein früher Vogel. Nach (1) fängt Lilly also den Wurm. Da nach (5) Doro ein Wurm ist, wird er von Lilly gefangen im Widerspruch zu (2).
- Nach dem ersten Teil ist Lilly ein Igel, und nach (7) steht sie um 5 Uhr auf. Dies ist nach (4) für Igel spät, Lilly ist also ein später Igel und somit ein spätes Tier.
- Da nach dem zweiten Teil Lilly ein später Igel ist und sie nach (2) Doro, die nach (5) ein Wurm ist, nicht fängt, fängt der späte Igel im Allgemeinen nicht 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
- Die rechte Seite ist gemäß
Korollar 2.5 (Diskrete Mathematik (Osnabrück 2026))
und
Satz 2.11 (Diskrete Mathematik (Osnabrück 2026))
gleich
was mit der linken Seite übereinstimmt.
- Es bezeichne
die Addition mit , und zu einer -elementigen Teilmenge bezeichne
die natürliche Nummerierung von gemäß der Ordnung von . Wir behaupten, dass die Abbildung
bijektiv ist. Die Abbildung ist wohldefiniert, da in der ersten Komponente eine -elementige Teilmenge von , in der zweiten Komponente eine bijektive Abbildung von nach und in der dritten Komponente eine bijektive Abbildung von nach steht. Wir geben explizit eine Umkehrabbildung an. Zu ist das Urbild die Permutation auf , die durch
gegeben ist. Hierbei gilt offenbar
und
und
daher wird unter der ersten Abbildung auf dieses Dreiertupel abgebildet und die erste Abbildung ist surjektiv. Die Injektivität ergibt sich daraus und dem ersten Teil.
Aufgabe (2 Punkte)
Zeige, dass in einem kommutativen Halbring die Beziehung gilt.
Dies ergibt sich aus
Aufgabe (2 Punkte)
Berechne
Es ist
Aufgabe (2 Punkte)
Bestimme, ob die durch die Relationstabelle
beschriebene Relation auf der Menge reflexiv, symmetrisch, transitiv, antisymmetrisch ist.
Die Relation ist nicht reflexiv, da nicht zu sich selbst in Beziehung steht. Die Relation ist symmetrisch, da die einzige Relationsbeziehung zwischen verschiedenen Elementen die Relation zwischen und ist, und diese in beide Richtungen gegeben ist. Daher ist die Relation auch nicht antisymmetrisch. Die Relation ist transitiv. Die einzige zu überprüfende nichttriviale Voraussetzung ist und , wobei die Konklusion wegen und gilt.
Aufgabe (3 Punkte)
Bestimme in mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von und .
Der Euklidische Algorithmus liefert:
Der größte gemeinsame Teiler von und ist also .
Aufgabe (1 Punkt)
Finde die Primfaktorzerlegung von
Es ist
wobei Primzahlen sind.
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.
Wegen
ist , die Relation ist also reflexiv. Es sei nun . Dies bedeutet
Somit ist auch
und damit ist auch , was die Symmetrie bedeutet. Es sei schließlich und . Dies bedeutet
und
Wegen der Abgeschlossenheit eines Untervektorraumes unter Addition gilt somit
was bedeutet. Dies ergibt die Transitivität.
Aufgabe (3 Punkte)
Es sei eine Gruppe. Zeige, dass sich Gruppenelemente und Gruppenhomomorphismen von nach über die Korrespondenz
entsprechen.
Es sei fixiert. Dass die Abbildung
ein Gruppenhomomorphismus ist, ist eine Umformulierung der Potenzgesetze. Wegen erhält man aus der Potenzabbildung das Gruppenelement zurück. Umgekehrt ist ein Gruppenhomomorphismus durch eindeutig festgelegt, da für positiv und für negativ gelten muss.
Aufgabe (2 Punkte)
Zeige, dass es keinen Ringhomomorphismus von nach gibt.
Nehmen wir an, dass
ein Ringhomomorphismus ist. Dann ist . In gilt , daher gilt in
Das würde aber bedeuten, dass die Gleichung in eine Lösung besitzt, was nicht der Fall ist.
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.
Es seien zunächst die Permutationen und zueinander konjugiert über die bijektive Abbildung
es gelte also
Aus der Zyklendarstellung (einschließlich der Fixpunkte)
ergibt sich gemäß Korollar 15.15 (Diskrete Mathematik (Osnabrück 2026))
Dabei sind die Zyklen der gleichen Länge wie und sie konstituieren zusammen die Zyklendarstellung von .
Es seien nun Permutationen und gegeben, die über den gleichen Typ verfügen. Wir wählen aus dem Wirkungsbereich eines jeden Zyklus von ein Element heraus, und wir wählen aus dem Wirkungsbereich eines jeden Zyklus (mit der gleichen Länge wie ) von ein Element heraus. Es besitzt jedes Element eine eindeutige Darstellung
mit einem und einem zwischen und der Länge des Zyklus . Entsprechend besitzt jedes Element eine eindeutige Darstellung
Wir betrachten nun die bijektive Abbildung , die auf abbildet. Diese ist bijektiv und erfüllt
sie stiftet also eine Konjugation zwischen und .
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 , .
Zur Folge der Quadratzahlen gehört als erzeugende Funktion die Potenzreihe . Wir gehen aus von der Identität
aus Beispiel 17.9 (Diskrete Mathematik (Osnabrück 2026)). Ableiten ergibt daraus die Identität
Multiplikation mit ergibt
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.
- Es seien
.
Aus
folgt direkt
Deshalb werden im Nullteilergraphen verbundene Knotenpunkte auf einem gemeinsamen Punkt abgebildet oder aber auf ein Punktepaar, das ebenfalls verbunden ist. Dies bedeutet schwacher Homomorphismus.
- Es sei und . Die zugehörige Multiplikationsabbildung ist die Nullabbildung, daher wird die Nullteilerkante zwischen und nicht auf eine Kante abgebildet, da die beiden Endpunkte vereinigt werden.
- Die Multiplikation mit ist genau dann bijektiv, wenn eine Einheit ist. In diesem Fall ist
äquivalent zu
da man ja mit der Einheit kürzen kann.
- Es sei , im zugehörigen Nullteilergraphen ist mit verbunden, sonst gibt es keine Verbindungen. Daher ist jede Permutation auf ein Graphautomorphismus. Davon gibt es , also kann schon allein aufgrund der Anzahl nicht jeder Graphautomorphismus von einer Multiplikation mit einer Einheit herkommen. Konkret ist die Transposition von und nicht durch eine Multiplikation gegeben, da eine Multiplikation, die auf abbildet, schon die Multiplikation mit sein muss. Doch diese schickt auf .
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 .
Es ist .
Das charakteristische Polynom ist
Somit sind Eigenwerte mit algebraischer und geometrischer Vielfachheit .
Der Eigenraum zu ist der Kern von . Dieser ist
Der Eigenraum zu ist der Kern von . Dieser ist
Der Eigenraum zu ist der Kern von . Dieser ist
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.
Es sei . Wir zeigen
indem wir die zulässigen Färbungen analysieren. Eine zulässige Färbung von ist eine zulässige Färbung von , bei der auch die Bedingung erfüllt ist. Somit müssen wir zeigen, dass die zulässigen Färbungen von mit den zulässigen Färbungen von entsprechen. Über den surjektiven schwachen Graphhomomorphismus
erhält man aus einer zulässigen Färbung von direkt eine (nichtzulässige) Färbung von mit identischem Wert auf und und damit direkt eine zulässige Färbung auf mit identischem Wert auf und . Diese Gesamtzuordnung ist injektiv. Wenn umgekehrt eine zulässige Färbung
mit gegeben ist, so kann man dies direkt als eine Färbung auf auffassen. Wenn eine Kante von ist, so liegt dieser Kante eine Kante in zugrunde, und daher überträgt sich die Zulässigkeit.
