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	5	6	9	0	7	0	0	0	0	0	58

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. Eine untere Schranke zu einer Teilmenge  ${}J\subseteq I$  in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Ein linearer Graph.
5. Ein Zyklus in einem Graphen  ${}G=(V,E)$. 
6. Die Paarungszahl eines bipartiten Graphen  ${}G=A\uplus B$. 

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

Es seien ${}n$ Geraden in der Ebene gegeben. Formuliere und beweise eine Formel (in Abhängigkeit von ${}n$) für die maximale Anzahl von Schnittpunkten der Geraden.

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 * (9 (2+3+4) Punkte)

Wir betrachten die reelle Matrix

${}M={\begin{pmatrix}1&1\\1&0\end{pmatrix}}\,.$

a) Bestimme

$M^{n}{\begin{pmatrix}1\\0\end{pmatrix}}$

für  ${}n=1,2,3,4$. 

b) Es sei

${}{\begin{pmatrix}x_{n+1}\\y_{n+1}\end{pmatrix}}:=M^{n}{\begin{pmatrix}1\\0\end{pmatrix}}\,.$

Erstelle eine Beziehung zwischen den Folgen ${}x_{n}$ und ${}y_{n}$ und Rekursionsformeln für diese Folgen.

c) Bestimme die Eigenwerte und die Eigenvektoren zu ${}M$.

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)