Kurs:Diskrete Mathematik/4/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	$\sum$
Punkte	3	3	7	6	2	3	5	2	2	3	7	1	3	10	8	65

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein kommutativer Halbring.
2. Eine ordnungsvolltreue Abbildung

   $F:M_1⟶M_2,x⟼F(x),$

   zwischen geordneten Mengen.

3. Die Restklassengruppe $G/H$ zu einer Untergruppe  $H\subseteq G$  in einer kommutativen Gruppe $G$.
4. Das Faseranzahltupel zu einer Abbildung $f:L\to M$ zwischen endlichen Mengen $L,M$.
5. Der Kontraktionsgraph zu einer Kante  $e=\{u,v\}$  in einem Graphen  $G=(V,E)$. 
6. Ein Baum.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über das inverse Element in einer Gruppe $(G,\circ ,e)$.
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 $2025$ weiß man, dass $17$ Tage sockenzerstreut und $11$ 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 $2023$ weiß man, dass $270$ Tage sockenzerstreut und $120$ 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

$M=\{a,b,c,d\}$

die durch die Tabelle

$\star$	$a$	$b$	$c$	$d$
$a$	$b$	$a$	$c$	$a$
$b$	$d$	$a$	$b$	$b$
$c$	$a$	$b$	$c$	$c$
$d$	$b$	$d$	$d$	$d$

gegebene Verknüpfung $\star$.

1. Berechne

   $b\star (a\star (d\star a)).$

2. Besitzt die Verknüpfung $\star$ ein neutrales Element?

Aufgabe * (3 Punkte)

Es sei  $R=𝔓(M)$  die Potenzmenge zu einer Menge $M$. Zeige, dass $R$ mit der Vereinigung $\cup$ als Addition und der leeren Menge als $0$ und mit dem Durchschnitt $\cap$ als Multiplikation und der Gesamtmenge $M$ als $1$ ein kommutativer Halbring ist.

Aufgabe * (5 Punkte)

Zeige, dass für  $n\ge 3$  die Abschätzung

$n^{n+1}\ge (n+1{)}^n$

gilt.

Aufgabe * (2 Punkte)

Es sei $M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge $𝔓(M)$, die durch

$S\preccurlyeq T,\text{ falls }\mathrm{\#}\left(S\right)\le \mathrm{\#}\left(T\right),$

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

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!

Aufgabe * (3 Punkte)

Bestimme das inverse Element zu $\overline{44}$ in $\mathbb{Z}/(97)$.

Aufgabe * (7 Punkte)

Es seien  $a,b\in ℂ$.  Wir schreiben

$\sum _{\ell =0}^{\mathrm{\infty }}(a+bt{)}^{\ell }{t}^{\ell }=\sum _m{c}_m{t}^m$

mit  $c_m\in ℂ$.  Zeige, dass diese Koeffizienten die Anfangsbedingungen  $c_0=1$,   $c_1=a$  und die Rekursionsbedingung

$c_{m+1}=a{c}_m+b{c}_{m-1}$

erfüllen.

Aufgabe (1 Punkt)

Skizziere ein Pfeildiagramm, das die nebenstehende Permutation überschneidungsfrei darstellt.

Aufgabe * (3 Punkte)

Beweise den Satz über die Gradsumme in einem Graphen.

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

Es sei $G$ ein Graph und $K$ der zugehörige Kantengraph.

1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

   $\Psi :\mathrm{Aut}G⟶\mathrm{Aut}K$

   gibt.

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

Aufgabe * (8 (5+3) Punkte)

Es sei $G$ der abgebildete Stiergraph.

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