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	5	6	1	0	4	4	0	0	5	1	3	0	0	0	4	47

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Menge/Permutation/Definition/Begriff
2. Geordnete Mengen/Abbildung/Ordnungstreu/Definition/Begriff
3. Die Quotientenmenge zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Ungerichteter Graph/Regulär/Definition/Begriff
5. Ungerichteter Graph/Kartesisches Produkt/Definition/Begriff
6. Ungerichter Graph/Optimale Paarung/Definition/Begriff

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'$ 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 * (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 ${}M_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei

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

Beweise die Anzahlformel

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

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 (0 Punkte)

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 * (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 (0 Punkte)

Aufgabe (0 Punkte)

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 * (1 Punkt)

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge ${}3$ 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 (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Beweise den Sechs-Farben-Satz.