Kurs:Diskrete Mathematik/6/Klausur mit Lösungen/kontrolle



Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Punkte 3 3 4 4 5 6 1 0 4 4 0 0 5 1 3 0 0 0 4 47




Aufgabe (3 Punkte)


Lösung


Aufgabe (3 Punkte)


Lösung

  1. Es seien und endliche Mengen mit bzw. Elementen. Dann besitzt die Produktmenge genau Elemente.
  2. Die Untergruppen von sind genau die Teilmengen der Form
    mit einer eindeutig bestimmten nicht-negativen Zahl .
  3. Ein Graph ist genau dann bipartit, wenn jeder Kreis in ihm geradzahlig ist.


Aufgabe (4 Punkte)

Es sei eine endliche Menge mit Elementen und sei ein Element, das nicht zu gehöre. Zeige, dass dann die Vereinigung genau Elemente besitzt.


Lösung

Wenn leer ist, so besteht die Vereinigungsmenge nur aus dem einzigen Element und steht somit in Bijektion zu . Allgemein liegt eine bijektive Abbildung

vor. Wir definieren eine Abbildung

durch

Dies ist wohldefiniert. Die Abbildung ist surjektiv, da alle Elemente aus durch Elemente aus getroffen werden und da durch getroffen wird. Die Abbildung ist auch injektiv. Wenn nämlich aus der Definitionsmenge sind, so ist, wenn beide zu gehören, direkt

Wenn hingegen ist, so ist und


Aufgabe (4 (2+2) Punkte)

Gabi Hochster möchte sich die Fingernägel ihrer linken Hand (ohne den Daumennagel) lackieren, wobei die drei Farben zur Verfügung stehen. Sie möchte nicht, dass zwei benachbarte Finger die gleiche Farbe bekommen.

  1. Wie viele Möglichkeiten gibt es, wenn sie nur zwei Farben verwendet?
  2. Wie viele Möglichkeiten gibt es, wenn sie alle drei Farben verwendet?


Lösung

  1. Wenn nur zwei Farben verwendet werden, sagen wir die Farben und , so legt die Farbe auf dem Zeigefinger alles weitere fest, nämlich oder . Da es drei Möglichkeiten gibt, aus drei Farben zwei Farben auszuwählen, gibt es sechs Möglichkeiten, die Nägel mit nur zwei Farben in der beschriebenen Weise zu lackieren.
  2. Wenn alle drei Farben vorkommen sollen, so kommt genau eine doppelt und die beiden anderen Farben einfach vor. Für die Wahl der doppelt verwendeten Farbe gibt es drei Möglichkeiten. Für die Auswahl der zwei Finger für diese Farbe gibt es grundsätzlich

    Möglichkeiten, davon sind aber drei Möglichkeiten durch die Nachbarschatsbedingung ausgeschlossen. In jedem dieser Fälle hat man noch zwei Möglichkeiten, wie man die beiden anderen Farben verteilen soll. Also gibt es von diesem Typ

    Möglichkeiten.


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

Es sei . Vergleiche die Anzahl der injektiven Abbildungen von einer -elementigen Menge in eine -elementige Menge mit der Anzahl der surjektiven Abbildungen von einer -elementigen Menge in eine -elementige Menge in den folgenden Fällen.

a) ,


b) ,


c) .


Lösung


a) Es gibt Abbildungen von einer einelementigen Menge in eine zweielementige Menge, die stets injektiv sind. Dagegen gibt es überhaupt nur eine Abbildung von einer zweielementigen Menge auf eine einelementige Menge, die natürlich surjektiv ist.


b) Wir betrachten injektive Abbildungen

Es gibt Möglichkeiten für und es gibt Möglichkeiten für (da ja schon besetzt ist), also insgesamt Möglichkeiten. Zur Bestimmung der surjektiven Abbildungen

überlegen wir uns, dass dabei Elemente auf ein gleiches Element abgebildet werden müssen. Dafür gibt es Paare. Für das Paar gibt es dann Möglichkeiten, wohin es abgebildet wird, also gibt es surjektive Abbildungen.


c) Wir betrachten injektive Abbildungen

Es gibt Möglichkeiten für , es gibt Möglichkeiten für (da ja schon besetzt ist) und es gibt Möglichkeiten für , also insgesamt Möglichkeiten. Zur Bestimmung der surjektiven Abbildungen

überlegen wir uns, dass dabei Elemente auf ein gleiches Element abgebildet werden müssen. In einer -elementigen Menge gibt es Paare. Wenn das Paar feststeht, so geht es um die Anzahl der bijektiven Abbildungen auf einer -elementigen Menge, das sind . Also gibt es insgesamt surjektive Abbildungen.


Aufgabe (6 Punkte)

Es sei eine Menge und es seien , , endliche Teilmengen. Für eine Teilmenge sei

Beweise die Anzahlformel


Lösung

Wir beweisen die Aussage durch Induktion über , wobei der Fall klar ist. Für siehe Aufgabe *****. {{:Kurs:Kurs:Diskrete Mathematik/Endliche Menge/Formel für Durchschnitt und Vereinigung/Aufgabe/Aufgabereferenznummer/Endliche Menge/Formel für Durchschnitt und Vereinigung/Aufgabe/Aufgabereferenznummer}} Es ist

wobei wir für die zweite Gleichung den Fall von zwei Teilmengen und für die dritte und die vierte Gleichung die Induktionsvoraussetzung verwendet haben. Für die fünfte Gleichung führen wir hinten die Indexverschiebung durch und der mittlere Term wird in die rechte Summe integriert. Die sechste Gleichung ergibt sich von unten nach oben gelesen, wenn man die Teilmengen

je nachdem aufspaltet, ob dazu gehört oder nicht.


Aufgabe (1 Punkt)

Es sei eine kommutative Gruppe und

ein surjektiver Gruppenhomomorphismus. Zeige, dass ebenfalls kommutativ ist.


Lösung

Es seien . Dann gibt es mit und . Dann ist


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 (1+3) Punkte)

Wir betrachten die Menge

die mit der stellenweisen Addition von Funktionen eine kommutative Gruppe ist. Auf dieser Menge bildet die Hintereinanderschaltung von Abbildungen eine assoziative Verknüpfung mit der Identität als neutralem Element.

  1. Zeige, dass das Distributivgesetz in der Form

    gilt.

  2. Zeige, dass das Distributivgesetz in der Form

    nicht gilt.


Lösung

  1. Es ist
    für alle , somit ist

    für beliebige .

  2. Es sei die Quadratabbildung, also

    und es sei

    die identische Abbildung, also

    Dann ist einerseits

    und andererseits

    Somit ist


Aufgabe (4 Punkte)

Zeige, dass beim euklidischen Algorithmus zu und der größte gemeinsame Teiler von zwei aufeinanderfolgenden Resten stets gleich bleibt und schließe daraus, dass der Algorithmus den größten gemeinsamen Teiler der beiden Zahlen berechnet.


Lösung

Die Reste seien mit bezeichnet. Wenn ein gemeinsamer Teiler von und von ist, so zeigt die Beziehung

dass auch ein Teiler von und damit ein gemeinsamer Teiler von und von ist. Die Umkehrung folgt genauso. Daraus folgt mit der Gleichungskette

dass der Algorithmus den größten gemeinsamen Teiler von und berechnet.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (5 (3+2) Punkte)

Es sei ein Graph.

  1. Zeige, dass für die folgenden Eigenschaften äquivalent sind.
    a) Es ist .
    b) Für alle folgt aus auch .
    c) Die Abbildung

    mit

    ist ein Graphhomomorphismus.

  2. Es sei die Relation aus (1). Welche Eigenschaften einer Ordnungsrelation erfüllt sie, welche nicht?


Lösung

  1. Die Äquivalenz von (1) und (2) ist klar. Es sei (2) erfüllt und sei die angegebene Abbildung. Wenn sind, so werden sie auf sich selbst abgebildet und daher bleiben Kanten erhalten. Sei . Es wird auf sich selbst und auf abgebildet. Wenn es eine Kante zwischen und gibt, dann nach (2) auch zwischen und . Es sei umgekehrt (3) erfüllt und sei . Dann ist und ist eine Kante. Da ein Graphhomomorphismus vorliegt, folgt, dass auch

    eine Kante ist, also auch .

  2. Wir argumentieren mit (1). Damit ist unmittelbar klar, dass diese Relation transitiv und reflexiv ist. Sie ist im Allgemeinen aber nicht antisymmetrisch. Betrachten wir den Graphen mit drei Punkten , wobei und Kanten seien und keine Kante. Dann ist

    und und stehen in Relation zueinander, sie sind aber nicht gleich.


Aufgabe (1 Punkt)

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge gibt.


Lösung


Aufgabe (3 (1+1+1) Punkte)

  1. Ist die abgebildete Paarung maximal?
  2. Skizziere eine optimale Paarung für den Graphen.
  3. Ist der Graph bipartit?


Lösung Graph/Paarung/Paarungszahl/1/Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (4 Punkte)

Beweise den Sechs-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 sechs Farben. Die Nachbarn von verwenden höchstens Farben davon und daher kann man für eine sechste Farbe wählen, was insgesamt eine zulässige Färbung von mit Farben ergibt.