Kurs:Diskrete Mathematik/12/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 | 4 | 7 | 6 | 1 | 3 | 0 | 0 | 3 | 3 | 0 | 2 | 0 | 9 | 0 | 0 | 0 | 47 |
Aufgabe (3 Punkte)
Definiere die folgenden (kursiv gedruckten) Begriffe.
- Ein Ring .
- Relation/Rechtseindeutig/Definition/Begriff
- Ein Gruppenhomomorphismus zwischen Gruppen und .
- Ungerichteter Graph/Untergraph/Voll/Definition/Begriff
- Ungerichteter Graph/Weg/Länge/Definition/Begriff
- Ungerichteter Graph/Gradmatrix/Definition/Begriff
- Eine Menge heißt ein Ring, wenn es zwei
Verknüpfungen
(genannt Addition und Multiplikation)
und (nicht notwendigerweise verschiedene) Elemente gibt, die die folgenden Eigenschaften erfüllen.
- Axiome der Addition
- Assoziativgesetz: Für alle gilt: .
- Kommutativgesetz: Für alle gilt .
- ist das neutrale Element der Addition, d.h. für alle ist .
- Existenz des Negativen: Zu jedem gibt es ein Element mit .
- Axiome der Multiplikation
- Assoziativgesetz: Für alle gilt: .
- ist das neutrale Element der Multiplikation, d.h. für alle ist .
- Distributivgesetz: Für alle gilt und .
- Relation/Rechtseindeutig/Definition/Begriff/Inhalt
- Eine
Abbildung
heißt Gruppenhomomorphismus, wenn die Gleichheit
für alle gilt.
- Ungerichteter Graph/Untergraph/Voll/Definition/Begriff/Inhalt
- Ungerichteter Graph/Weg/Länge/Definition/Begriff/Inhalt
- Ungerichteter Graph/Gradmatrix/Definition/Begriff/Inhalt
Aufgabe (3 Punkte)
Formuliere die folgenden Sätze.
- Der Satz über die Division mit Rest für die ganzen Zahlen.
- Der Multinomialsatz für einen kommutativen Halbring.
- Die eulersche Polyederformel.
- Es sei eine fixierte positive natürliche Zahl. Dann gibt es zu jeder ganzen Zahl eine eindeutig bestimmte ganze Zahl und eine eindeutig bestimmte natürliche Zahl
, , mit
- Es sei ein
kommutativer Halbring
und seien
Elemente und
.
Dann ist
- Es sei ein
zusammenhängender
planarer Graph
mit Knotenpunkten, Kanten und Gebieten. Dann gilt die eulersche Polyederformel
Aufgabe (3 Punkte)
Bestimme die Anzahl der Tripel mit
Wenn fixiert ist, so muss
sein. D.h. läuft zwischen und und legt dabei eindeutig fest. Somit gibt es bei fixiertem genau Möglichkeiten. Da ist, gibt es insgesamt also
erlaubte Tripel.
Aufgabe (4 Punkte)
Es seien und Mengen und seien und Teilmengen. Zeige die Gleichheit
Wir zeigen die beiden Inklusionen. Es sei zunächst
Dies bedeutet
und
Dies bedeutet einerseits und andererseits . Also ist .
Wenn umgekehrt gilt, so ist und . Wegen der Teilmengenbeziehungen und ist
und
und damit auch
Aufgabe (7 Punkte)
Beweise den Satz über die Anzahl von fixpunktfreien Permutationen.
Zu jedem sei die Menge aller Permutationen auf , die auf sich selbst abbilden. Somit ist die Menge aller Permutationen, die mindestens einen Fixpunkt haben. Um die Siebformel anwenden zu können, müssen wir zu die Durchschnitte verstehen. Bei dieser Menge handelt es sich um diejenigen Permutationen, für die alle Elemente aus Fixpunkte sind (und die auch noch weitere Fixpunkte außerhalb von haben können). Wenn die Anzahl von gleich ist, so gibt es solche Permutationen, da ja die Permutation auf die Identität sein muss und es außerhalb von keine Einschränkung gibt. Bei fixiertem wissen wir auch, wie viele Teilmengen mit Elementen zu berücksichtigen sind, nämlich . Mit diesen Zahlen ergibt sich nun mit Hilfe der Siebformel der Ausdruck
Somit ist die Anzahl der fixpunktfreien Permutationen gleich
Aufgabe (6 (1+1+1+1+2) Punkte)
Wir definieren die Folge (der sogenannten Bernoulli-Zahlen) , , durch und für durch die rekursive Bedingung
- Berechne .
- Berechne .
- Berechne .
- Berechne .
- Zeige, dass alle rationale Zahlen sind.
- Für
ist die rekursive Bedingung gleich
- Für
ist die rekursive Bedingung gleich
- Für
ist die rekursive Bedingung gleich
- Für
ist die rekursive Bedingung gleich
- Wir zeigen die Aussage durch Induktion nach , wobei der Induktionsanfang bereits erledigt ist. Zum Beweis des Induktionsschrittes nehmen wir an, das die Rationalität von bereits bekannt sei. Die Rekursionsbedingung
schreiben wir als
bzw. als
Da die Binomialkoeffizienten natürliche Zahlen sind, steht hier wieder eine rationale Zahl.
Aufgabe (1 Punkt)
Die Gaußklammer definiert keinen Gruppenhomomorphismus, da ist und damit
aber
ist.
Aufgabe (3 Punkte)
Es sei ein kommutativer Ring. Zu jedem sei
die Multiplikation mit . Zeige, dass genau dann bijektiv ist, wenn es surjektiv ist.
Man zeige durch ein Beispiel, dass in dieser Situation aus der Injektivität nicht die Bijektivität folgt.
Die Bijektivität impliziert nach Definition stets die Surjektivität. Es sei surjektiv. Dann gibt es insbesondere ein Urbild der , also ein Element mit . Dies bedeutet, dass eine Einheit ist. Wegen der Distributivität ist die Abbildung ein Gruppenhomomorphismus der additiven Gruppe . Um die Injektivität zu zeigen wenden wir das Kernkriterium an. Es sei also . Dann ist aber
Element besteht.
Es sei . Dann ist die Multiplikation mit injektiv, aber nicht surjektiv, da nur gerade Zahlen im Bild liegen.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (3 Punkte)
Es seien ganze Zahlen und die davon erzeugte Untergruppe. Zeige, dass eine ganze Zahl genau dann ein gemeinsamer Teiler der ist, wenn ist, und dass genau dann ein größter gemeinsamer Teiler ist, wenn ist.
Aus folgt sofort für jedes , was gerade bedeutet, dass diese Zahlen teilt, also ein gemeinsamer Teiler ist. Es sei umgekehrt ein gemeinsamer Teiler. Dann ist und da die kleinste Untergruppe ist, die alle enthält, muss gelten.
Aufgrund von Satz 8.4 (Diskrete Mathematik (Osnabrück 2020)) wissen wir, dass es eine ganze Zahl gibt mit . Für einen anderen gemeinsamen Teiler der gilt , so dass von allen anderen gemeinsamen Teilern geteilt wird, also ein größter gemeinsamer Teiler ist.
Aufgabe (3 Punkte)
Es seien und endliche Mengen mit bzw. Elementen und sei
eine Abbildung. Wie viele Abbildungen
mit
gibt es?
Die Elemente aus seien mit bezeichnet. Zu jedem sei
und
die Anzahl der Elemente aus , die auf abgebildet werden (was sein kann). Da
gelten soll, muss für jedes gelten. Somit gibt es
Möglichkeiten für solche Abbildungen.
Aufgabe (0 Punkte)
Aufgabe (2 Punkte)
Bestimme die Automorphismengruppe des abgebildeten Graphen.
Der isolierte Punkt muss unter einem Graphautomorphismus auf sich selbst abgebildet werden. und können offenbar miteinander vertauscht werden. Deshalb gibt es neben der Identität diese Vertauschung und die Automorphismengruppe ist .
Aufgabe (0 Punkte)
Aufgabe (9 Punkte)
Beweise den Fünf-Farben-Satz.
Wir führen Induktion über die Anzahl der Knoten, wobei die Aussage bei höchstens Knoten unmittelbar klar ist. Es liege also ein ebener Graph mit Knoten vor und für jeden ebenen Graphen mit weniger als Knoten wissen wir, dass es eine zulässige Färbung mit höchstens Farben gibt. Nach Korollar 25.6 (Diskrete Mathematik (Osnabrück 2020)) (2) gibt es einen Knoten mit höchstens Nachbarn. Es sei der Graph, der aus entsteht, wenn man und die an anliegenden Kanten herausnimmt. Nach Induktionsvoraussetzung besitzt eine zulässige Färbung mit höchstens fünf Farben. Wenn die Nachbarn von nur höchstens vier Farben verwenden, was insbesondere dann der Fall ist, wenn höchstens vier Nachbarn besitzt, so kann man unmittelbar eine zulässige Färbung von zu einer zulässigen Färbung von ausbauen, indem man eine Farbe gibt, die in seinen Nachbarn nicht vorkommt.
Der Punkt habe also genau Nachbarn mit verschiedenen Farben. Wir fixieren eine ebene Realisierung und wir bezeichnen die Nachbarn von mit im Uhrzeigersinn (ein kleiner Kreis um in , der keinen weiteren Knotenpunkt enthält, trifft jeden Verbindungsweg zu den Nachbarn in einem Punkt der Peripherie, dies legt die Reihenfolge fest). Es sei eine zulässige Färbung auf . Wie betrachten den induzierten Untergraphen
Wir machen nun eine Fallunterscheidung je nachdem, ob und in miteinander durch einen Weg verbunden sind oder nicht.
Fall 1. Sie sind nicht miteinander verbunden. Es sei die Zusammenhangskomponente von , die enthält. Dabei gilt . Wir legen jetzt auf eine neue Färbung fest, indem wir
festlegen. Für die Knoten aus werden also die beiden Farben und vertauscht, alle anderen Knoten behalten ihre Farben. Diese Färbung ist wieder zulässig. Dies ist klar für Kanten, die ganz außerhalb von oder ganz innerhalb von verlaufen. Bei und besitzt bei dieser Knoten eine von und verschiedene Farbe, und bei gibt es keine Kante.
Fall 2. Es gibt nun einen verbindenen Weg in von nach . Wenn es keinen verbindenden Weg von nach innerhalb des entsprechend definierten Untergraphen gibt, so sind wir aufgrund der Argumentation im ersten Fall fertig. Wir sind somit in der Situation, wo es einen Weg von nach in und einen Weg von nach in gibt. Wir ergänzen durch die Kanten und zu einem Zykel in , der in der ebenen Realisierung einem geschlossenen Weg entspricht (indem wir ohne Knotenwiederholungen wählen, können wir diesen geschlossenen Weg als überschneidungsfrei annehmen). Hierbei liegt einer der Punkte oder im Inneren des durch den Weg begrenzten Gebietes und der andere außerhalb davon. Dann gibt es aber eine Überschneidung der beiden Wege, und diese muss in einem Knotenpunkt vorliegen. Dies ist aber ein Widerspruch, da die Farben alle verschieden sind.
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)
Aufgabe (0 Punkte)