Kurs:Diskrete Mathematik/4/Klausur

Aus Wikiversity
Zur Navigation springen Zur Suche springen


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.


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.


Aufgabe * (7 Punkte)

Beweise den Satz über die Multiplikation und endliche Mengen.


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.


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?


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.


Aufgabe * (5 Punkte)

Zeige, dass für die Abschätzung

gilt.


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?


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

Europäische Wasserscheiden.png

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.


Aufgabe * (3 Punkte)

Bestimme das inverse Element zu in .


Aufgabe * (3 Punkte)

Beweise den Satz über die Gradsumme in einem Graphen.


Aufgabe (0 Punkte)


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.


Aufgabe (0 Punkte)


Aufgabe * (8 (5+3) Punkte)

Bull graph.circo.svg

Es sei der abgebildete Stiergraph.

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


Aufgabe * (2 Punkte)

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