Kurs:Diskrete Mathematik/11/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	0	4	0	3	4	0	0	1	0	4	0	0	0	0	0	0	25

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein kommutativer Ring ${}R$.
2. Eine Relation auf einer Menge ${}M$.
3. Die Folge der euklidischen Reste zu ganzen Zahlen ${}a,b$ mit ${}b\neq 0$.
4. Die Automorphismengruppe eines ungerichteten Graphen ${}G$.
5. Der Umfang eines zyklischen Graphen ${}G$.
6. Eine zulässige Färbung eines Graphen ${}G=(V,E)$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Beziehung zwischen der Addition und endlichen Mengen.
2. Der Satz über die Restklassenkörper von ${}\mathbb {Z}$.
3. Der Rekursionssatz für aufspannende Bäume.

Aufgabe * (3 Punkte)

Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?

Aufgabe (0 Punkte)

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

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(n,k)\longmapsto {\binom {n}{k}},$

wobei bei ${}k>n$ der Binomialkoeffizient als ${}0$ zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

1. Besitzt diese Verknüpfung ein neutrales Element von links?
2. Besitzt diese Verknüpfung ein neutrales Element von rechts?
3. Bestimme ${}{\binom {\binom {3}{2}}{1}}$ und ${}{\binom {3}{\binom {2}{1}}}$.
4. Ist diese Verknüpfung assoziativ?

Aufgabe (0 Punkte)

Aufgabe (3 Punkte)

Es sei ${}M$ ein Monoid, ${}a,b\in M$ und ${}m,n\in \mathbb {N}$. Zeige die folgenden Potenzgesetze.

1. ${}a^{m+n}=a^{m}\cdot a^{n}\,.$

2. ${}(a^{m})^{n}=a^{mn}\,.$

3. Wenn ${}M$ kommutativ ist, so ist

   ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,.$

Aufgabe * (4 Punkte)

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Ordnung auf ${}M$. Zeige durch Induktion über ${}n\geq 2$ die Aussage: Wenn für Elemente ${}a_{1},\ldots ,a_{n}\in M$ die Beziehung

${}a_{1}\preccurlyeq a_{2}\preccurlyeq \ldots \preccurlyeq a_{n-1}\preccurlyeq a_{n}\,$

und

${}a_{n}\preccurlyeq a_{1}\,$

gilt, dann sind alle ${}a_{1},\ldots ,a_{n}$ gleich.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe * (1 Punkt)

Finde eine Darstellung der ${}1$ für das Zahlenpaar ${}11$ und ${}13$.

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Es sei ${}G$ eine Gruppe. Betrachte die Relation ${}\sim$ auf ${}G$, die durch

$x\sim y{\text{ genau dann, wenn }}x=y{\text{ oder }}x=y^{-1}$

erklärt ist. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)

Aufgabe (0 Punkte)