Kurs:Diskrete Mathematik/6/Klausur/kontrolle

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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (4 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Es sei ${}G$ eine kommutative Gruppe und

$\varphi \colon G\longrightarrow H$

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

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (4 (1+3) Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (5 (3+2) Punkte)Referenznummer erstellen

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)Referenznummer erstellen

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge ${}3$ gibt.

Aufgabe (3 (1+1+1) Punkte)Referenznummer erstellen

1. Ist die abgebildete Paarung maximal?
2. Skizziere eine optimale Paarung für den Graphen.
3. Ist der Graph bipartit?

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (4 Punkte)Referenznummer erstellen

Beweise den Sechs-Farben-Satz.