Kurs:Diskrete Mathematik/10/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	2	2	3	3	3	6	6	0	6	0	0	7	0	0	0	0	0	44

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein neutrales Element ${}e\in M$ zu einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.$

2. Die Symmetrie einer Relation ${}R$ auf einer Menge ${}M$.
3. Geordnete Menge/Teilmenge/Untere Schranke/Definition/Begriff
4. Ungerichteter Graph/Pfad/Definition/Begriff
5. Ungerichteter Graph/Zyklus/Definition/Begriff
6. Ungerichter Graph/Paarungszahl/Definition/Begriff

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Wohldefiniertheit der Anzahl.
2. Das allgemeine Distributivgesetz für einen kommutativen Halbring.
3. Der Satz von Kirchhoff über die Anzahl der Spannbäume.

Aufgabe * (2 Punkte)

Es sei ${}a\in \mathbb {N} _{+}$. Zeige, wie man ${}a^{10}$ mit vier Multiplikationen berechnen kann.

Aufgabe * (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. Wie viele Möglichkeiten gibt es?

Aufgabe * (3 Punkte)

Zeige, dass die Binomialkoeffizienten die rekursive Beziehung

${}{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}}\,$

erfüllen.

Aufgabe * (3 Punkte)

Es sei ${}G$ eine zweielementige Menge. Erstelle eine Verknüpfungstabelle für die Verknüpfung „Vereinigung“ auf der Potenzmenge ${}{\mathfrak {P}}\,(G)$.

Aufgabe (3 Punkte)

Beweise das folgende Untergruppenkriterium. Eine nichtleere Teilmenge ${}H\subseteq G$ einer Gruppe ${}G$ ist genau dann eine Untergruppe, wenn gilt:

${\text{ für alle }}g,h\in H{\text{ ist }}gh^{-1}\in H.$

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

Zu ${}n\in \mathbb {N}$ sei

${}[n]=\{0,1,2,\ldots ,n\}\,.$

Zu jedem ${}n\in \mathbb {N}$ und jedem ${}0\leq k\leq n$ seien die Abbildungen

$D_{k}\colon [n]\longrightarrow [n+1]$

durch

${}D_{k}(j)={\begin{cases}j,{\text{ falls }}j<k,\\j+1{\text{ sonst}},\end{cases}}\,$

und die Abbildungen

$S_{k}\colon [n+1]\longrightarrow [n]$

durch

${}S_{k}(j)={\begin{cases}j,{\text{ falls }}j\leq k,\\j-1{\text{ sonst}},\end{cases}}\,$

definiert.

a) Erstelle eine Wertetabelle für

$D_{3}\colon [4]\longrightarrow [5].$

b) Erstelle eine Wertetabelle für

$S_{3}\colon [6]\longrightarrow [5].$

c) Beschreibe die durch die Wertetabelle

${}j$	${}0$	${}1$	${}2$	${}3$	${}4$	${}5$
${}\varphi (j)$	${}0$	${}2$	${}2$	${}4$	${}5$	${}5$

gegebene Abbildung

$\varphi \colon [5]\longrightarrow [5]$

als eine Hintereinanderschaltung von geeigneten ${}D_{k}$ und ${}S_{i}$.

Aufgabe * (6 Punkte)

Beweise das Lemma von Bezout für teilerfremde natürliche Zahlen ${}a$ und ${}b$ durch Induktion über das Maximum von ${}a$ und ${}b$.

Aufgabe (0 Punkte)

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

Es sei ${}M$ die Menge der zweimal stetig differenzierbaren Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$. Definiere auf ${}M$ eine Relation durch

$f\sim g{\text{ falls }}f(0)=g(0),\,f'(0)=g'(0){\text{ und }}f^{\prime \prime }(1)=g^{\prime \prime }(1).$

a) Zeige, dass dies eine Äquivalenzrelation ist.

b) Finde für jede Äquivalenzklasse dieser Äquivalenzrelation einen polynomialen Vertreter.

c) Zeige, dass diese Äquivalenzrelation mit der Addition von Funktionen verträglich ist.

d) Zeige, dass diese Äquivalenzrelation nicht mit der Multiplikation von Funktionen verträglich ist.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (7 Punkte)

Beweise den Charakterisierungssatz für Bäume.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)