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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	${}\sum$
Punkte	3	3	7	6	2	3	5	2	2	3	3	0	10	0	8	2	59

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein kommutativer Halbring.
2. Eine ordnungsvolltreue Abbildung.
3. Die Restklassengruppe ${}G/H$ zu einer Untergruppe ${}H\subseteq G$ in einer kommutativen Gruppe ${}G$.
4. Ein isolierter Knoten in einem Graphen.
5. Der Kontraktionsgraph zu einer Kante ${}e$ in einem Graphen ${}G=(V,E)$.
6. Ein Baum.

Lösung

1. Ein kommutativer Halbring ${}R$ ist eine Menge mit Verknüpfungen ${}+$ und ${}\cdot$ und mit zwei ausgezeichneten Elementen ${}0$ und ${}1$ derart, dass folgende Bedingungen erfüllt sind:
   1. Die Addition ist eine kommutative, assoziative Verknüpfung, für die ${}0$ das neutrale Element ist.
   2. Die Multiplikation ist eine kommutative, assoziative Verknüpfung, für die ${}1$ das neutrale Element ist.
   3. Es gilt das Distributivgesetz, also

      ${}a\cdot (b+c)=(a\cdot b)+(a\cdot c)\,$

      für alle ${}a,b,c\in R$.
2. Geordnete Mengen/Abbildung/Ordnungsvolltreu/Definition/Begriff/Inhalt
3. Die Restklassengruppe ist die Quotientenmenge ${}G/\sim _{H}$ mit der eindeutig bestimmten Gruppenstruktur.
4. Ungerichteter Graph/Isolierter Knoten/Definition/Begriff/Inhalt
5. Ungerichteter Graph/Kontraktionsgraph/Definition/Begriff/Inhalt
6. Ungerichteter Graph/Baum/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über das inverse Element in einer Gruppe ${}(G,\circ ,e)$.
2. Die Rekursionsformel für die Anzahl der surjektiven Abbildungen.
3. Der Satz über das chromatische Polynom.

Lösung

1. Zu jedem ${}x\in G$ ist das Element ${}y\in G$ mit

   ${}x\circ y=e\,$

   eindeutig bestimmt.
2. Zu ${}n,k\in \mathbb {N}$ bezeichne ${}\operatorname {Surj} (n,k)$ die Anzahl der surjektiven Abbildungen einer ${}n$-elementigen Menge in eine ${}k$-elementige Menge. Dann gilt die Rekursionsformel

   ${}\operatorname {Surj} (n+1,k)=k\cdot \operatorname {Surj} (n,k)+k\cdot \operatorname {Surj} (n,k-1)\,.$

3. Das chromatische Polynom ${}P_{G}$ zu einem Graphen mit ${}n$ Knotenpunkten ist ein normiertes Polynom vom Grad ${}n$.

Aufgabe (7 Punkte)

Beweise den Satz über die Multiplikation und endliche Mengen.

Lösung

Wir behaupten, dass die Abbildung

$\psi \colon \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\longrightarrow \{1,2,\ldots ,mn\},\,(i,j)\longmapsto (i-1)n+j,$

bijektiv ist. Zum Beweis der Surjektivität sei ${}z\in \{1,2,\ldots ,mn\}$ vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

$\{1,\ldots ,n\}\cup \{n+1,\ldots ,2n\}\cup \{2n+1,\ldots ,3n\}\cup \ldots \cup \{(m-1)n+1,\ldots ,mn\}$

unterteilen. Das Element ${}z$ gehört somit zu einem dieser Intervalle, d.h. es gibt ein ${}i$ mit

${}z\in \{(i-1)n+1,\ldots ,in\}\,$

mit ${}i$ zwischen ${}1$ und ${}m$. Dann ist

${}z=(i-1)n+j\,$

mit einem ${}j$ zwischen ${}1$ und ${}n$ und gehört somit zum Bild. Zum Beweis der Injektivität seien

${}(i,j),(k,\ell )\in \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\,$

gegeben, die auf das gleiche Element abbilden. Es gilt also

${}(i-1)n+j=(k-1)n+\ell \,.$

Da ${}j$ und ${}\ell$ beide zu ${}{\{1,\ldots ,n\}}$ gehören, sind die Summen jeweils maximal gleich ${}in$ bzw. ${}kn$. Daher können die Zahlen nur dann gleich sein, wenn

${}i=k\,$

und dann nach der Abziehregel auch

${}j=\ell \,$

ist.

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

Professor Knopfloch kommt gelegentlich mit verschiedenen Socken und/oder mit verschiedenen Schuhen in die Universität. Er legt folgende Definitionen fest.

1. Ein Tag heißt sockenzerstreut, wenn er verschiedene Socken anhat.
2. Ein Tag heißt schuhzerstreut, wenn er verschiedene Schuhe anhat.
3. Ein Tag heißt zerstreut, wenn er sockenzerstreut oder schuhzerstreut ist.
4. Ein Tag heißt total zerstreut, wenn er sowohl sockenzerstreut als auch schuhzerstreut ist.

a) Vom Jahr ${}2015$ weiß man, dass ${}17$ Tage sockenzerstreut und ${}11$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal zerstreut? Wie viele Tage waren in diesem Jahr maximal total zerstreut und wie viele Tage waren minimal total zerstreut?

b) Vom Jahr ${}2013$ weiß man, dass ${}270$ Tage sockenzerstreut und ${}120$ Tage schuhzerstreut waren. Wie viele Tage waren in diesem Jahr maximal zerstreut und wie viele Tage waren minimal total zerstreut?

c) Erstelle eine Formel, die die Anzahl der sockenzerstreuten, der schuhzerstreuten, der zerstreuten und der total zerstreuten Tage in einem Jahr miteinander in Verbindung bringt.

Lösung

a) Zerstreutheit: Die sockenzerstreuten Tage sind jedenfalls zerstreut. Das Minimum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind ${}17$. Das Maximum ergibt sich, wenn kein Tag gleichzeitig sockenzerstreut und schuhzerstreut war, das ergibt ${}28$ Tage.

Totale Zerstreutheit: Die total zerstreuten Tage sind insbesondere schuhzerstreut. Das Maximum ergibt sich, wenn alle schuhzerstreuten Tage auch sockenzerstreut waren, das sind ${}11$ Tage. Das Minimum ergibt sich, wenn kein Tag gleichzeitig schuh- und sockenzerstreut war, also ${}0$.

b) Wegen

${}270+120=390\geq 365\,$

können alle Jahre des Tages zerstreut gewesen sein, also ${}365$. Minimal waren ${}25$ Tage total zerstreut.

c) Es sei ${}s$ die Anzahl der sockenzerstreuten Tage, ${}x$ die Anzahl der schuhzerstreuten Tage, ${}z$ die Anzahl der zerstreuten Tage und ${}t$ die Anzahl der total zerstreuten Tage. Dann gilt die Formel

${}s+x=z+t\,.$

Beide Seiten der Formel sind additiv in den Tagen, sie muss also nur für einen Tag nachgewiesen werden. Wenn der Tag nicht zerstreut ist, steht beidseitig ${}0$. Wenn der Tag sockenzerstreut ist, aber nicht schuhzerstreut (oder umgekehrt), so ist der Tag zerstreut, aber nicht total zerstreut, und beidseitig steht ${}1$. Wenn der Tag total zerstreut ist, so steht beidseitig ${}2$.

Aufgabe (2 (1+1) Punkte)

Wir betrachten auf der Menge

${}M=\{a,b,c,d\}\,$

die durch die Tabelle

${}\star$	${}a$	${}b$	${}c$	${}d$
${}a$	${}b$	${}a$	${}c$	${}a$
${}b$	${}d$	${}a$	${}b$	${}b$
${}c$	${}a$	${}b$	${}c$	${}c$
${}d$	${}b$	${}d$	${}d$	${}d$

gegebene Verknüpfung ${}\star$.

1. Berechne

   $b\star (a\star (d\star a)).$

2. Besitzt die Verknüpfung ${}\star$ ein neutrales Element?

Lösung

1. Es ist

   ${}b\star (a\star (d\star a))=b\star (a\star b)=b\star a=d\,.$

2. Es gibt kein neutrales Element, da dann eine Zeile eine Wiederholung der Leitzeile sein müsste, was nicht der Fall ist.

Aufgabe (3 Punkte)

Es sei ${}R={\mathfrak {P}}\,(M)$ die Potenzmenge zu einer Menge ${}M$. Zeige, dass ${}R$ mit der Vereinigung ${}\cup$ als Addition und der leeren Menge als ${}0$ und mit dem Durchschnitt ${}\cap$ als Multiplikation und der Gesamtmenge ${}M$ als ${}1$ ein kommutativer Halbring ist.

Lösung

Die Eigenschaften sind allenfalls bis auf das Distributivgesetz klar. Letzteres besagt die Identität

${}A\cap (B\cup C)={\left(A\cap B\right)}\cup {\left(A\cap C\right)}\,.$

Wenn ein Element ${}x$ links dazugehört, so gehört es zu ${}A$ und es gehört zu ${}B\cup C$. Somit gehört es zu ${}B$ oder zu ${}C$ und damit auch zu ${}A\cap B$ oder zu ${}A\cap C$, also jedenfalls zur rechten Seite. Wenn es rechts dazu gehört, sagen wir zu ${}A\cap B$, was wir wegen der Symmetrie der Situation annehmen können, so gehört es erst recht zu ${}A\cap (B\cup C)$.

Aufgabe (5 Punkte)

Zeige, dass für ${}n\geq 3$ die Abschätzung

${}n^{n+1}\geq (n+1)^{n}\,$

gilt.

Lösung

Es ist

${}n^{n+1}=n\cdot n^{n}\,$

und

${}(n+1)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}n^{n-k}=n^{n}+n\cdot n^{n-1}+{\binom {n}{2}}n^{n-2}+\cdots +{\binom {n}{n-1}}n^{1}+1\,.$

Hier stehen ${}n+1$ Summanden, wobei der allerletzte gleich ${}1$ ist. Wir vergleichen die Summanden mit ${}n^{n}$. Die ersten beiden Summanden sind gleich ${}n^{n}$, für ${}k\geq 2$ ist

${}{\binom {n}{k}}n^{n-k}={\frac {n(n-1)\cdots (n-k+1)}{k!}}n^{n-k}<n^{k}\cdot n^{n-k}=n^{n}\,.$

Bei

${}n\geq 3\,$

sind somit insbesondere die letzten beiden Summanden zusammengenommen kleinergleich ${}n^{n}$ und die Summe rechts ist somit ${}\leq n\cdot n^{n}$.

Aufgabe (2 Punkte)

Es sei ${}M$ eine endliche Menge. Betrachte die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch

$S\preccurlyeq T,{\text{ falls }}{\#\left(S\right)}\leq {\#\left(T\right)},$

gegeben ist. Handelt es sich dabei um eine Ordnungsrelation?

Lösung

Das ist keine Ordnungsrelation, da die Antisymmetrie nicht erfüllt ist. Wenn man zwei verschiedene Teilmengen aus ${}M$ nimmt, sagen wir ${}S$ und ${}T$, die beide die gleiche Anzahl besitzen (was es gibt, sobald ${}M$ zumindest zwei Elemente besitzt), so gilt ${}{\#\left(S\right)}={\#\left(T\right)}$ und damit

${}S\preccurlyeq T\,$

und

${}T\preccurlyeq S\,,$

aber daraus kann nicht auf ${}S=T$ geschlossen werden.

Aufgabe (2 (0.5+0.5+0.5+0.5) Punkte)

Wir nennen zwei Flüsse in Europa äquivalent, wenn sie letztlich in das gleiche Meer entwässern, wobei wir die Einteilungen der Karte übernehmen.

1. Wie viele Äquialenzklassen gibt es?
2. Ist der Rhein zur Donau äquivalent?
3. Ist die Hase zur Themse äquivalent?
4. Man gebe zwei Repräsentanten für die Äquivalenzklasse Ostsee an.

Lösung

1. Es gibt ${}8$ Äquivalenzklassen gemäß der Karte: Atlantik, Nordee, Ostsee, Polarmeer, Mittelmeer, Adria, Schwarzes Meer, Kaspisches Meer.
2. Donau und Rhein sind nicht äquivalent, da die Donau in das Schwarze Meer und der Rhein in die Nordsee fließt.
3. Themse und Hase sind äquivalent, da sie beide (die Hase über die Ems) in die Nordsee fließen.
4. Oder und Weichsel sind Repräsentanten für Flüsse, die in die Ostsee fließen.

Aufgabe (3 Punkte)

Bestimme das inverse Element zu ${}{\overline {44}}$ in ${}\mathbb {Z} /(97)$.

Lösung

Der euklidische Algorithmus liefert

${}97=2\cdot 44+9\,,$

${}44=4\cdot 9+8\,,$

${}9=1\cdot 8+1\,.$

Somit ist

${}{\begin{aligned}1&=9-1\cdot 8\\&=9-1\cdot (44-4\cdot 9)\\&=5\cdot 9-1\cdot 44\\&=5\cdot (97-2\cdot 44)-1\cdot 44\\&=5\cdot 97-11\cdot 44.\end{aligned}}$

Daher ist

${}-11=86\,$

das inverse Element zu ${}44$ in ${}\mathbb {Z} /(97)$.

Aufgabe (3 Punkte)

Beweise den Satz über die Gradsumme in einem Graphen.

Lösung

Das kann man beispielsweise durch Induktion über die Anzahl der Kanten bei gegebener Knotenmenge beweisen. Beim einem kantenlosen Graphen steht links und rechts beidseitig ${}0$. Wenn man zu einem Graphen eine Kante hinzutut, sagen wir die Kante, die die beiden Punkte ${}u$ und ${}v$ verbindet, so erhöht sich der Grad von ${}u$ und der Grad von ${}v$ jeweils um ${}1$ und die anderen Grade bleiben unverändert. Somit erhöhen sich beide Seiten um ${}2$.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (10 (5+2+3) Punkte)

Es sei ${}G$ ein Graph und ${}K$ der zugehörige Kantengraph.

1. Zeige, dass es einen natürlichen Gruppenhomomorphismus

   $\Psi \colon \operatorname {Aut} \,G\longrightarrow \operatorname {Aut} \,K$

   gibt.

2. Zeige, dass die Abbildung ${}\Psi$ nicht injektiv sein muss.
3. Zeige, dass die Abbildung ${}\Psi$ nicht surjektiv sein muss.

Lösung

1. Wir definieren

   $\operatorname {Aut} \,G\longrightarrow \operatorname {Aut} \,K,\,f\longmapsto \Psi (f):={\left(\{u,v\}\mapsto \{f(u),f(v)\}\right)}.$

   Einem Automorphismus ${}f$ des Graphen wird also die Abbildung auf der Kantenmenge zugeordet, die eine Kante auf die Bildkante (!) unter ${}f$ abbildet. Die Gesamtabbildung ist wegen

   ${}{\begin{aligned}(\Psi (f\circ g))(\{u,v\})&=\{(f\circ g)(u),(f\circ g)(v)\}\\&=\{f(g(u)),f(g(v))\}\\&=(\Psi (f))(\{g(u),g(v)\})\\&=(\Psi (f))((\Psi (g))(\{u,v\}))\\&=(\Psi (f)\circ \Psi (g))(\{u,v\})\end{aligned}}$

   ein Homomorphismus in das Monoid der Abbildungen auf der Kantenmenge. Wegen

   ${}\Psi (f)\circ \Psi (f^{-1})=\Psi (f\circ f^{-1}))=\operatorname {Id} _{K}\,$

   gehört das Bild von ${}\Psi$ zur Permutationsgruppe der Kantenmenge. Es ist noch zu zeigen, dass ${}\Psi (f)$ ein Automorphismus des Kantengraphen ist. Es sei also ${}f$ ein Graphautomorphismus und seien ${}e,e'\in K$ Kanten, die im Kantengraph adjazent sind. Das bedeutet, dass sie im Graphen ${}G$ koinzident sind und daher ist ${}e=\{u,v\}$ und ${}e'=\{u,w\}$. Dann sind auch ${}\Psi (f)(e)=\{f(u),f(v)\}$ und ${}\Psi (f)(e')=\{f(u),f(w)\}$ koinzident und somit adjazent im Kantengraphen.

2. Wir betrachten den linearen Graphen mit zwei Punkten. Seine Automorphismengruppe ist neben der Identität durch die Vertauschung der beiden Punkte gegeben. Der Kantengraph ist einpunktig und hat triviale Automorphismengruppe.

3. 

   

   
   

   Es sei ${}G$ der vollständige Graph zu vier Punkten mit dem zugehörigen Kantengraphen (siehe Skizzen). Wir betrachten den Automorphismus des Kantengraphen, der ${}b$ und ${}d$ vertauscht und ${}a,c,e,f$ auf sich selbst abbildet. Da sowohl ${}b$ als auch ${}d$ im Kantengraphen mit ${}a,c,e,f$ verbunden sind, liegt ein Automorphismus vor. Wir behaupten, dass man diesen nicht durch einen Graphautomorphismus von ${}G$ realisieren kann. Es sei ${}h$ ein solcher Homomorphismus. Da die Kanten ${}a$ und ${}e$ auf sich selbst abgebildet werden, muss ${}1$ auf sich abgebildet werden. Deshalb müssen auch ${}2$ und ${}3$ auf sich selbst abgebildet werden und ${}h$ muss die Identität sein. Dann ist aber auch ${}\Psi (h)$ die Identität.

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (8 (5+3) Punkte)

Es sei ${}G$ der abgebildete Stiergraph.

1. Bestimme das charakteristische Polynom von ${}G$.
2. Bestimme das chromatische Polynom von ${}G$.

Lösung

1. Wir nummerieren die Knotenpunkte von links nach rechts und von oben nach unten. Die Adjazenzmatrix ist

   ${\begin{pmatrix}0&0&1&0&0\\0&0&0&1&0\\1&0&0&1&1\\0&1&1&0&1\\0&0&1&1&0\end{pmatrix}}.$

   Das charakteristische Polynom ist die Determinante von

   ${\begin{pmatrix}X&0&-1&0&0\\0&X&0&-1&0\\-1&0&X&-1&-1\\0&-1&-1&X&-1\\0&0&-1&-1&X\end{pmatrix}}.$

   Wir entwickelen nach der ersten Spalte und erhalten

   ${}{\begin{aligned}\chi _{}&=X\cdot \det {\begin{pmatrix}X&0&-1&0\\0&X&-1&-1\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}-\det {\begin{pmatrix}0&-1&0&0\\X&0&-1&0\\-1&-1&X&-1\\0&-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}-X\det {\begin{pmatrix}0&-1&0\\X&-1&-1\\-1&-1&X\end{pmatrix}}+X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}\cdot \det {\begin{pmatrix}X&-1&-1\\-1&X&-1\\-1&-1&X\end{pmatrix}}+2X\det {\begin{pmatrix}-1&0&0\\-1&X&-1\\-1&-1&X\end{pmatrix}}+\det {\begin{pmatrix}-1&0&0\\0&-1&0\\-1&-1&X\end{pmatrix}}\\&=X^{2}{\left(X(X^{2}-1)+(-X-1)-(1+X)\right)}-2X(X^{2}-1)+X\\&=X{\left(X{\left(X(X^{2}-1)-2X-2\right)}-2(X^{2}-1)+1\right)}\\&=X{\left(X^{4}-5X^{2}-2X+3\right)}\end{aligned}}$

2. Eine zulässige Färbung ist insbesondere eine Färbung des Stierkopfes. Dieser ist ein vollständiger Graph mit drei Knotenpunkten und sein chromatisches Polynom ist ${}X(X-1)(X-2)$. Jede zulässige Färbung kann man auf den ganzen Stier zulässig ausdehnen, wobei für die Hörner jeweils nur die Farbe der anliegenden Schläfe ausgeschlossen ist. Deshalb ist das chromatische Polynom gleich

   ${}X(X-1)(X-2)(X-1)^{2}=X(X-1)^{3}(X-2)\,.$

Aufgabe (2 Punkte)

Ist der Spielzuggraph zur Schachfigur König auf einem ${}5\times 5$-Feld planar?

Lösung

Der Spielzuggraph zum König auf einem ${}5\times 5$-Feld ist nicht planar. Er besitzt ${}20$ horizontale Kanten, ${}20$ vertikale Kanten und ${}2\cdot 16$ diagonale Kanten. Deshalb gibt es insgesamt ${}72$ Kanten. Bei einem planaren Graphen mit ${}25$ Knoten darf es aber nach Korollar 25.6 (Diskrete Mathematik (Osnabrück 2020))  (1) höchstens

${}3\cdot 25-6=69\,$

Kanten geben.