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


Aufgabe 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Punkte 3 3 7 6 2 3 5 2 2 3 3 0 10 0 8 2 59




Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

  1. Ein kommutativer Halbring.
  2. Eine ordnungsvolltreue Abbildung.
  3. Die Restklassengruppe zu einer Untergruppe in einer kommutativen Gruppe .
  4. Ein isolierter Knoten in einem Graphen.
  5. Der Kontraktionsgraph zu einer Kante in einem Graphen .
  6. Ein Baum.


Lösung

  1. Ein kommutativer Halbring ist eine Menge mit Verknüpfungen und und mit zwei ausgezeichneten Elementen und derart, dass folgende Bedingungen erfüllt sind:
    1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
    2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die das neutrale Element ist.
    3. Es gilt das Distributivgesetz, also
      für alle .
  2. Geordnete Mengen/Abbildung/Ordnungsvolltreu/Definition/Begriff/Inhalt
  3. Die Restklassengruppe ist die Quotientenmenge mit der eindeutig bestimmten Gruppenstruktur.
  4. Ungerichteter Graph/Isolierter Knoten/Definition/Begriff/Inhalt
  5. Ungerichteter Graph/Kontraktionsgraph/Definition/Begriff/Inhalt
  6. Ungerichteter Graph/Baum/Definition/Begriff/Inhalt


Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

  1. Der Satz über das inverse Element in einer Gruppe .
  2. Die Rekursionsformel für die Anzahl der surjektiven Abbildungen.
  3. Der Satz über das chromatische Polynom.


Lösung

  1. Zu jedem ist das Element mit
    eindeutig bestimmt.
  2. Zu bezeichne die Anzahl der surjektiven Abbildungen einer -elementigen Menge in eine -elementige Menge. Dann gilt die Rekursionsformel
  3. Das chromatische Polynom zu einem Graphen mit Knotenpunkten ist ein normiertes Polynom vom Grad .


Aufgabe (7 Punkte)

Beweise den Satz über die Multiplikation und endliche Mengen.


Lösung

Wir behaupten, dass die Abbildung

bijektiv ist. Zum Beweis der Surjektivität sei vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

unterteilen. Das Element gehört somit zu einem dieser Intervalle, d.h. es gibt ein mit

mit zwischen und . Dann ist

mit einem zwischen und und gehört somit zum Bild. Zum Beweis der Injektivität seien

gegeben, die auf das gleiche Element abbilden. Es gilt also

Da und beide zu gehören, sind die Summen jeweils maximal gleich bzw. . Daher können die Zahlen nur dann gleich sein, wenn

und dann nach der Abziehregel auch

ist.


Aufgabe (6 (2+1+3) Punkte)

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

  1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
  2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
  3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
  4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr weiß man, dass Tage sockenzerstreut und Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.


Lösung

a) Zerstreutheit: Die sockenzerstreuten Tage sind jedenfalls zerstreut. Das Minimum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind . Das Maximum ergibt sich, wenn kein Tag gleichzeitig sockenzerstreut und schuhzerstreut war, das ergibt Tage.

Totale Zerstreutheit: Die total zerstreuten Tage sind insbesondere schuhzerstreut. Das Maximum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind Tage. Das Minimum ergibt sich, wenn kein Tag gleichzeitig schuh- und sockenzerstreut war, also .

b) Wegen

können alle Jahre des Tages zerstreut gewesen sein, also . Minimal waren Tage total zerstreut.

c) Es sei die Anzahl der sockenzerstreuten Tage, die Anzahl der schuhzerstreuten Tage, die Anzahl der zerstreuten Tage und die Anzahl der total zerstreuten Tage. Dann gilt die Formel

Beide Seiten der Formel sind additiv in den Tagen, sie muss also nur für einen Tag nachgewiesen werden. Wenn der Tag nicht zerstreut ist, steht beidseitig . Wenn der Tag sockenzerstreut ist, aber nicht schuhzerstreut (oder umgekehrt), so ist der Tag zerstreut, aber nicht total zerstreut, und beidseitig steht . Wenn der Tag total zerstreut ist, so steht beidseitig .


Aufgabe (2 (1+1) Punkte)

Wir betrachten auf der Menge

die durch die Tabelle

gegebene Verknüpfung .

  1. Berechne
  2. Besitzt die Verknüpfung ein neutrales Element?


Lösung

  1. Es ist
  2. Es gibt kein neutrales Element, da dann eine Zeile eine Wiederholung der Leitzeile sein müsste, was nicht der Fall ist.


Aufgabe (3 Punkte)

Es sei die Potenzmenge zu einer Menge . Zeige, dass mit der Vereinigung als Addition und der leeren Menge als und mit dem Durchschnitt als Multiplikation und der Gesamtmenge als ein kommutativer Halbring ist.


Lösung

Die Eigenschaften sind allenfalls bis auf das Distributivgesetz klar. Letzteres besagt die Identität

Wenn ein Element links dazugehört, so gehört es zu und es gehört zu . Somit gehört es zu oder zu und damit auch zu oder zu , also jedenfalls zur rechten Seite. Wenn es rechts dazu gehört, sagen wir zu , was wir wegen der Symmetrie der Situation annehmen können, so gehört es erst recht zu .


Aufgabe (5 Punkte)

Zeige, dass für die Abschätzung

gilt.


Lösung

Es ist

und

Hier stehen Summanden, wobei der allerletzte gleich ist. Wir vergleichen die Summanden mit . Die ersten beiden Summanden sind gleich , für ist

Bei

sind somit insbesondere die letzten beiden Summanden zusammengenommen kleinergleich und die Summe rechts ist somit .


Aufgabe (2 Punkte)

Es sei eine endliche Menge. Betrachte die Relation auf der Potenzmenge , die durch

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?


Lösung

Das ist keine Ordnungsrelation, da die Antisymmetrie nicht erfüllt ist. Wenn man zwei verschiedene Teilmengen aus nimmt, sagen wir und , die beide die gleiche Anzahl besitzen (was es gibt, sobald zumindest zwei Elemente besitzt), so gilt und damit

und

aber daraus kann nicht auf geschlossen werden.


Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Wir nennen zwei Flüsse in Europa äquivalent, wenn sie letztlich in das gleiche Meer entwässern, wobei wir die Einteilungen der Karte übernehmen.

  1. Wie viele Äquialenzklassen gibt es?
  2. Ist der Rhein zur Donau äquivalent?
  3. Ist die Hase zur Themse äquivalent?
  4. Man gebe zwei Repräsentanten für die Äquivalenzklasse Ostsee an.


Lösung

  1. Es gibt Äquivalenzklassen gemäß der Karte: Atlantik, Nordee, Ostsee, Polarmeer, Mittelmeer, Adria, Schwarzes Meer, Kaspisches Meer.
  2. Donau und Rhein sind nicht äquivalent, da die Donau in das Schwarze Meer und der Rhein in die Nordsee fließt.
  3. Themse und Hase sind äquivalent, da sie beide (die Hase über die Ems) in die Nordsee fließen.
  4. Oder und Weichsel sind Repräsentanten für Flüsse, die in die Ostsee fließen.


Aufgabe (3 Punkte)

Bestimme das inverse Element zu in .


Lösung

Der euklidische Algorithmus liefert

Somit ist

Daher ist

das inverse Element zu in .


Aufgabe (3 Punkte)

Beweise den Satz über die Gradsumme in einem Graphen.


Lösung

Das kann man beispielsweise durch Induktion über die Anzahl der Kanten bei gegebener Knotenmenge beweisen. Beim einem kantenlosen Graphen steht links und rechts beidseitig . Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte und verbindet, so erhöht sich der Grad von und der Grad von jeweils um und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um .


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (10 (5+2+3) Punkte)

Es sei ein Graph und der zugehörige Kantengraph.

  1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

    gibt.

  2. Zeige, dass die Abbildung nicht injektiv sein muss.
  3. Zeige, dass die Abbildung nicht surjektiv sein muss.


Lösung

  1. Wir definieren

    Einem Automorphismus des Graphen wird also die Abbildung auf der Kantenmenge zugeordet, die eine Kante auf die Bildkante (!) unter abbildet. Die Gesamtabbildung ist wegen

    ein Homomorphismus in das Monoid der Abbildungen auf der Kantenmenge. Wegen

    gehört das Bild von zur Permutationsgruppe der Kantenmenge. Es ist noch zu zeigen, dass ein Automorphismus des Kantengraphen ist. Es sei also ein Graphautomorphismus und seien Kanten, die im Kantengraph adjazent sind. Das bedeutet, dass sie im Graphen koinzident sind und daher ist und . Dann sind auch und koinzident und somit adjazent im Kantengraphen.

  2. Wir betrachten den linearen Graphen mit zwei Punkten. Seine Automorphismengruppe ist neben der Identität durch die Vertauschung der beiden Punkte gegeben. Der Kantengraph ist einpunktig und hat triviale Automorphismengruppe.

  3. Es sei der vollständige Graph zu vier Punkten mit dem zugehörigen Kantengraphen (siehe Skizzen). Wir betrachten den Automorphismus des Kantengraphen, der und vertauscht und auf sich selbst abbildet. Da sowohl als auch im Kantengraphen mit verbunden sind, liegt ein Automorphismus vor. Wir behaupten, dass man diesen nicht durch einen Graphautomorphismus von realisieren kann. Es sei ein solcher Homomorphismus. Da die Kanten und auf sich selbst abgebildet werden, muss auf sich abgebildet werden. Deshalb müssen auch und auf sich selbst abgebildet werden und muss die Identität sein. Dann ist aber auch die Identität.


Aufgabe (0 Punkte)


Lösung /Aufgabe/Lösung


Aufgabe (8 (5+3) Punkte)

Es sei der abgebildete Stiergraph.

  1. Bestimme das charakteristische Polynom von .
  2. Bestimme das chromatische Polynom von .


Lösung

  1. Wir nummerieren die Knotenpunkte von links nach rechts und von oben nach unten. Die Adjazenzmatrix ist

    Das charakteristische Polynom ist die Determinante von

    Wir entwickelen nach der ersten Spalte und erhalten

  2. Eine zulässige Färbung ist insbesondere eine Färbung des Stierkopfes. Dieser ist ein vollständiger Graph mit drei Knotenpunkten und sein chromatisches Polynom ist . Jede zulässige Färbung kann man auf den ganzen Stier zulässig ausdehnen, wobei für die Hörner jeweils nur die Farbe der anliegenden Schläfe ausgeschlossen ist. Deshalb ist das chromatische Polynom gleich


Aufgabe (2 Punkte)

Ist der Spielzuggraph zur Schachfigur König auf einem -Feld planar?


Lösung

Der Spielzuggraph zum König auf einem -Feld ist nicht planar. Er besitzt horizontale Kanten, vertikale Kanten und diagonale Kanten. Deshalb gibt es insgesamt Kanten. Bei einem planaren Graphen mit Knoten darf es aber nach Korollar 25.6 (Diskrete Mathematik (Osnabrück 2020))  (1) höchstens

Kanten geben.