Kurs:Diskrete Mathematik/12/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	3	4	7	6	1	3	0	0	3	3	0	2	0	9	0	0	0	47

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Ring ${}R$.
2. Eine rechtseindeutige Relation  ${}R\subseteq M\times N$. 
3. Ein Gruppenhomomorphismus zwischen Gruppen ${}(G,\circ ,e_{G})$ und ${}(H,\circ ,e_{H})$.
4. Ein voller Untergraph  ${}(W,F)\subseteq (V,E)$. 
5. Die Länge eines Weges in einem Graphen.
6. Die Gradmatrix zu einem Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Division mit Rest für die ganzen Zahlen.
2. Der Multinomialsatz für einen kommutativen Halbring.
3. Die eulersche Polyederformel.

Aufgabe * (3 Punkte)

Bestimme die Anzahl der Tripel ${}(i,j,k)\in \mathbb {N} ^{3}$ mit

${}i+j+k=5\,.$

Aufgabe * (4 Punkte)

Es seien ${}M$ und ${}N$ Mengen und seien  ${}A\subseteq M$  und  ${}B\subseteq N$  Teilmengen. Zeige die Gleichheit

${}{\left(A\times N\right)}\cap {\left(M\times B\right)}=A\times B\,.$

Aufgabe * (7 Punkte)

Beweise den Satz über die Anzahl von fixpunktfreien Permutationen.

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

Wir definieren die Folge (der sogenannten Bernoulli-Zahlen) ${}B_{n}$, ${}n\in \mathbb {N}$, durch  ${}B_{0}=1$  und für  ${}n\geq 1$  durch die rekursive Bedingung

${}\sum _{j=0}^{n}{\binom {n+1}{j}}B_{j}=0\,.$

1. Berechne ${}B_{1}$.
2. Berechne ${}B_{2}$.
3. Berechne ${}B_{3}$.
4. Berechne ${}B_{4}$.
5. Zeige, dass alle ${}B_{n}$ rationale Zahlen sind.

Aufgabe * (1 Punkt)

Bestimme, ob die durch die Gaußklammer gegebene Abbildung

$\mathbb {Q} \longrightarrow \mathbb {Z} ,\,q\longmapsto \lfloor q\rfloor ,$

ein Gruppenhomomorphismus ist oder nicht.

Aufgabe * (3 Punkte)

Es sei ${}R$ ein kommutativer Ring. Zu jedem ${}f\in R$ sei

$\mu _{f}\colon R\longrightarrow R,\,g\longmapsto fg,$

die Multiplikation mit ${}f$. Zeige, dass ${}\mu _{f}$ genau dann bijektiv ist, wenn es surjektiv ist.

Man zeige durch ein Beispiel, dass in dieser Situation aus der Injektivität nicht die Bijektivität folgt.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen und  ${}H=(a_{1},\ldots ,a_{k})={\left\{n_{1}a_{1}+n_{2}a_{2}+\cdots +n_{k}a_{k}\mid n_{j}\in \mathbb {Z} \right\}}$  die davon erzeugte Untergruppe. Zeige, dass eine ganze Zahl ${}t$ genau dann ein gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$ ist, wenn  ${}H\subseteq \mathbb {Z} t$  ist, und dass ${}t$ genau dann ein größter gemeinsamer Teiler ist, wenn  ${}H=\mathbb {Z} t$  ist.

Aufgabe * (3 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen und sei

$f\colon M\longrightarrow N$

eine Abbildung. Wie viele Abbildungen

$s\colon N\longrightarrow M$

mit

${}f\circ s=\operatorname {Id} _{N}\,$

gibt es?

Aufgabe (0 Punkte)

Aufgabe * (2 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe (0 Punkte)

Aufgabe * (9 Punkte)

Beweise den Fünf-Farben-Satz.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)