Kurs:Diskrete Mathematik/11/Klausur mit Lösungen

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)$.

Lösung

1. Ein Ring ${}R$ heißt kommutativ, wenn die Multiplikation kommutativ ist.
2. Eine Relation ${}R$ auf einer Menge ${}M$ ist eine Teilmenge der Produktmenge ${}M\times M$, also ${}R\subseteq M\times M$.
3. Man nennt die durch die Anfangsbedingungen ${}r_{0}=a$ und ${}r_{1}=b$ und die mittels der Division mit Rest

   ${}r_{i}=q_{i}r_{i+1}+r_{i+2}\,$

   rekursiv bestimmte Folge ${}r_{i}$ die Folge der euklidischen Reste.

4. Zu einem Graphen ${}G$ nennt man die Gruppe aller Automorphismen

   $\varphi \colon G\longrightarrow G$

   die Automorphismengruppe von ${}G$.

5. Der Umfang eines zyklischen Graphen ${}G$ ist die längste Länge eines Kreises in Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikiversity.org/v1/“:): {\displaystyle {{}} G} .
6. Eine Färbung

   $f\colon V\longrightarrow B$

   heißt zulässig, wenn benachbarte Knotenpunkte stets eine verschiedene Farbe bekommen.

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.

Lösung

1. Es seien ${}M$ und ${}N$ disjunkte endliche Mengen mit ${}m$ bzw. ${}n$ Elementen. Dann besitzt ihre Vereinigung ${}M\cup N$ gerade ${}m+n$ Elemente.
2. Es sei ${}n\in \mathbb {N}$. Der Restklassenring ${}\mathbb {Z} /(n)$ ist genau dann ein Körper, wenn ${}n$ eine Primzahl ist.
3. Es sei ${}G$ ein schleifenfreier Multigraph und ${}e$ eine Kante von ${}G$. Dann besteht für die Anzahl der aufspannenden Bäume der Zusammenhang

   ${}t(G)=t(G\setminus e)+t(G/e)\,.$

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?

Lösung

Das Pickelpaar und die drei übrigen einzelnen Pickel können als vier Pickelfelder betrachtet werden, die in beliebiger Reihenfolge beackert werden könnnen. Dafür gibt es ${}4!=24$ Möglichkeiten. Bei jeder dieser Reihenfolge hat man beim Pickelpaar die freie Wahlmöglichkeit, welcher zuerst drankommt. Daher gibt es insgesamt

$2\cdot 24=48$

Möglichkeiten.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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?

Lösung

1. Es kann kein neutrales Element von links geben, da für ${}k>n$ gilt

   ${}{\binom {n}{k}}=0\neq k\,.$

2. ${}1$ ist das neutrale Element von rechts. Für ${}n\geq 1$ ist

   ${}{\binom {n}{1}}=n\,$

   und dies gilt auch für ${}n=0$.

3. Es ist

   ${}{\binom {\binom {3}{2}}{1}}={\binom {3}{1}}=3\,$

   und

   ${}{\binom {3}{\binom {2}{1}}}={\binom {3}{2}}=3\,.$

4. Die Verknüpfung ist nich assoziativ, beispielsweise ist

   ${}{\binom {\binom {4}{3}}{2}}={\binom {4}{2}}=6\,,$

   aber

   ${}{\binom {4}{\binom {3}{2}}}={\binom {4}{3}}=4\,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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}\,.$

Lösung Monoid/Potenzgesetze/Fakt/Beweis/Aufgabe/Lösung

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.

Lösung

Der Induktionsanfang ${}n=2$ folgt unmittelbar aus der Antisymmetrie. Es sei also die Aussage für ein gewisses ${}n\geq 2$ schon bewiesen und es liegen ${}n+1$ Elemente mit den Abschätzungen

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

und

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

vor. Wegen der Transitivität der Ordnung gilt dann auch

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

und damit gelten auch die Bedingungen in der Induktionsvoraussetzung. Somit ist also

${}a_{1}=a_{2}=\ldots =a_{n}\,.$

Wegen

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

und

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

stimmt auch ${}a_{n+1}$ mit diesem Element überein.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (1 Punkt)

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

Lösung

Es ist

${}6\cdot 11-5\cdot 13=66-65=1\,.$

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

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.

Lösung

Die Relation ist offenbar reflexiv. Zum Nachweis der Symmetrie sei ${}x\sim y$. Im Fall ${}x=y$ ist natürlich auch ${}y=x$ und somit ${}y\sim x$. Im Fall

${}x=y^{-1}\,$

ergibt sich durch Invertieren der Gleichung

${}x^{-1}={\left(y^{-1}\right)}^{-1}=y\,,$

also ebenfalls ${}y\sim x$. Zum Nachweis der Transitivität sei ${}x\sim y$ und ${}y\sim z$. Hier gibt es insgesamt vier Fälle. Bei ${}x=y$ und ${}y=z$ ist natürlich ${}x=z$. Bei ${}x=y$ und ${}y=z^{-1}$ ist ${}x=z^{-1}$, also ${}x\sim z$. Bei ${}x=y^{-1}$ und ${}y=z$ ist ${}x=y^{-1}=z^{-1}$, also wieder ${}x\sim z$. Bei ${}x=y^{-1}$ und ${}y=z^{-1}$ ist

${}x=y^{-1}={\left(z^{-1}\right)}^{-1}=z\,,$

also ${}x\sim z$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung