Kurs:Diskrete Mathematik/12/Klausur mit Lösungen

Aus Wikiversity



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.

  1. Ein Ring .
  2. Relation/Rechtseindeutig/Definition/Begriff
  3. Ein Gruppenhomomorphismus zwischen Gruppen und .
  4. Ungerichteter Graph/Untergraph/Voll/Definition/Begriff
  5. Ungerichteter Graph/Weg/Länge/Definition/Begriff
  6. Ungerichteter Graph/Gradmatrix/Definition/Begriff


Lösung

  1. 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.

    1. Axiome der Addition
      1. Assoziativgesetz: Für alle gilt: .
      2. Kommutativgesetz: Für alle gilt .
      3. ist das neutrale Element der Addition, d.h. für alle ist .
      4. Existenz des Negativen: Zu jedem gibt es ein Element mit .
    2. Axiome der Multiplikation
      1. Assoziativgesetz: Für alle gilt: .
      2. ist das neutrale Element der Multiplikation, d.h. für alle ist .
    3. Distributivgesetz: Für alle gilt und .
  2. Relation/Rechtseindeutig/Definition/Begriff/Inhalt
  3. Eine Abbildung

    heißt Gruppenhomomorphismus, wenn die Gleichheit

    für alle gilt.

  4. Ungerichteter Graph/Untergraph/Voll/Definition/Begriff/Inhalt
  5. Ungerichteter Graph/Weg/Länge/Definition/Begriff/Inhalt
  6. Ungerichteter Graph/Gradmatrix/Definition/Begriff/Inhalt


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über die Division mit Rest für die ganzen Zahlen.
  2. Der Multinomialsatz für einen kommutativen Halbring.
  3. Die eulersche Polyederformel.


Lösung

  1. 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
  2. Es sei ein kommutativer Halbring und seien Elemente und . Dann ist
  3. 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


Lösung

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


Lösung

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.


Lösung

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

  1. Berechne .
  2. Berechne .
  3. Berechne .
  4. Berechne .
  5. Zeige, dass alle rationale Zahlen sind.


Lösung

  1. Für ist die rekursive Bedingung gleich
    also ist .
  2. Für ist die rekursive Bedingung gleich
    also ist .
  3. Für ist die rekursive Bedingung gleich
    also ist .
  4. Für ist die rekursive Bedingung gleich
    also ist .
  5. 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)

Bestimme, ob die durch die Gaußklammer gegebene Abbildung

ein Gruppenhomomorphismus ist oder nicht.


Lösung

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.


Lösung

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

so dass der Kern nur aus einem

Element besteht.

Es sei . Dann ist die Multiplikation mit injektiv, aber nicht surjektiv, da nur gerade Zahlen im Bild liegen.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


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.


Lösung

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?


Lösung

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)


Lösung /Aufgabe/Lösung


Aufgabe (2 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Graphen.


Lösung

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)


Lösung /Aufgabe/Lösung


Aufgabe (9 Punkte)

Beweise den Fünf-Farben-Satz.


Lösung

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)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung