Kurs:Diskrete Mathematik/6/Klausur

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	${}\sum$
Punkte	3	3	4	4	2	5	6	4	4	4	1	1	4	2	5	3	2	3	4	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Permutation ${}\sigma$ auf einer Menge ${}M$.
2. Eine ordnungstreue Abbildung

   $F\colon M_{1}\longrightarrow M_{2},$

   zwischen den geordneten Mengen ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$.

3. Die Quotientenmenge zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Es sei  ${}R_{1}\subseteq M_{1}\times N_{1}$  eine Relation zwischen ${}M_{1}$ und ${}N_{1}$ und  ${}R_{2}\subseteq M_{2}\times N_{2}$  eine Relation zwischen ${}M_{2}$ und ${}N_{2}$. Wann nennt man die beiden Relationen isomorph?
5. Das kartesische Produkt der beiden Graphen ${}G=(V,E)$ und ${}H=(W,F)$.
6. Eine optimale Paarung  ${}P\subseteq E$  in einem Graphen ${}G$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Beziehung zwischen der Multiplikation und endlichen Mengen.
2. Der Satz über die Untergruppen von ${}\mathbb {Z}$.
3. Der Charakterisierungssatz für bipartite Graphen mittels Kreisen.

Aufgabe * (4 Punkte)

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen und sei ${}w$ ein Element, das nicht zu ${}M$ gehöre. Zeige, dass dann die Vereinigung ${}M\cup \{w\}$ genau ${}n^{\prime }$ Elemente besitzt.

Aufgabe * (4 (2+2) Punkte)

Gabi Hochster möchte sich die Fingernägel ihrer linken Hand (ohne den Daumennagel) lackieren, wobei die drei Farben ${}B,G,R$ 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?

Aufgabe * (2 Punkte)

Bestimme die Anzahl der hinteren Nullen in der Dezimalentwicklung von ${}100!$.

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

Es sei ${}n\in \mathbb {N} _{+}$. Vergleiche die Anzahl der injektiven Abbildungen von einer ${}n$-elementigen Menge in eine ${}n+1$-elementige Menge mit der Anzahl der surjektiven Abbildungen von einer ${}n+1$-elementigen Menge in eine ${}n$-elementige Menge in den folgenden Fällen.

a) ${}n=1$,

b) ${}n=2$,

c) ${}n=3$.

Aufgabe * (6 Punkte)

Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge  ${}J\subseteq \{1,\ldots ,n\}$  sei

${}A_{J}=\bigcap _{i\in J}A_{i}\,.$

Beweise die Anzahlformel (Siebformel)

${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)\,.$

Aufgabe * (4 Punkte)

Es seien drei verschiedene Zahlen  ${}a,b,c>1$  gegeben. Wie viele Teiler besitzt das Produkt ${}a\cdot b\cdot c$ minimal?

Aufgabe * (4 Punkte)

Zeige, dass beim euklidischen Algorithmus zu ${}a$ und ${}b$ 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.

Aufgabe * (4 (1+3) Punkte)

Wir betrachten die Menge

${}M=\operatorname {Abb} \,\left(\mathbb {R} ,\mathbb {R} \right)\,,$

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

1. Zeige, dass das Distributivgesetz in der Form

   ${}(f+g)\circ h=f\circ h+g\circ h\,$

   gilt.

2. Zeige, dass das Distributivgesetz in der Form

   ${}h\circ (f+g)=h\circ f+h\circ g\,$

   nicht gilt.

Aufgabe * (1 Punkt)

Es sei ${}G$ eine kommutative Gruppe und

$\varphi \colon G\longrightarrow H$

ein surjektiver Gruppenhomomorphismus. Zeige, dass ${}H$ ebenfalls kommutativ ist.

Aufgabe * (1 Punkt)

Wir betrachten die durch die Wertetabelle

${}x$	${}a$	${}b$	${}c$	${}d$	${}e$	${}f$	${}g$	${}h$
${}\psi (x)$	${}v$	${}w$	${}w$	${}u$	${}u$	${}v$	${}w$	${}z$

gegebene Abbildung

$\psi \colon \{a,b,c,d,e,f,g,h\}\longrightarrow \{u,v,w,y,z\}.$

Bestimme das zugehörige Faseranzahltupel.

Aufgabe * (4 (2+1+1) Punkte)

Eine Geldfälscherin stellt ${}3$- und ${}7$-Euro-Scheine her.

1. Zeige, dass es nur endlich viele (volle) Eurobeträge gibt, die sie nicht (exakt) begleichen kann.
2. Was ist der höchste Betrag, den sie nicht begleichen kann?
3. Beschreibe (ohne weitere Begründung) die Menge ${}M$ der Eurobeträge, die sie mit ihren Scheinen nicht begleichen kann.

Aufgabe * (2 Punkte)

Im ${}n$-Land gibt es Münzen zum Nennwert ${}1,n,n+1$ (mit ${}n\geq 2$). Zeige, dass die minimale Darstellung eines Geldbetrages im Allgemeinen nicht eindeutig ist.

Aufgabe * (5 (3+2) Punkte)

Es sei  ${}G=(V,E)$  ein Graph.

1. Zeige, dass für  ${}x,y\in V$  die folgenden Eigenschaften äquivalent sind.
   a) Es ist  ${}N(x)\subseteq N(y)$. 
   b) Für alle  ${}z\in V$  folgt aus  ${}xz\in E$  auch  ${}yz\in E$. 
   c) Die Abbildung

   $\varphi \colon V\longrightarrow V$

   mit

   ${}\varphi (u)={\begin{cases}u\,,{\text{ für }}u\neq x\,,\\y\,,{\text{ für }}u=x\,,\end{cases}}\,$

   ist ein Graphhomomorphismus.

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

Aufgabe (3 Punkte)

Zeige, dass der abgebildete Graph starr ist.

Aufgabe * (2 Punkte)

Es sei  ${}G=(V,E)$  ein zusammenhängender bipartiter Graph. Zeige, dass es nur eine (bis auf die Rolle der Teile) bipartite Zerlegung  ${}V=A\uplus B$  gibt.

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?

Aufgabe * (4 Punkte)

Beweise den Sechs-Farben-Satz.