Kurs:Diskrete Mathematik/1/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	2	5	5	2	2	0	7	3	6	2	3	4	6	9	62

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Potenzmenge zu einer Menge ${}M$.
2. Ein minimales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Ein Repräsentantensystem zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Der Maximalgrad eines Graphen ${}G=(V,E)$.
5. Ein Wald.
6. Die Knotenüberdeckungszahl eines Graphen ${}G=(V,E)$.

Lösung

1. Zu einer Menge ${}M$ nennt man die Menge aller Teilmengen von ${}M$ die Potenzmenge von ${}M$.
2. Ein Element ${}x\in I$ heißt minimal, wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}y\preccurlyeq x$ gibt.
3. Eine Teilmenge ${}T\subseteq M$ heißt ein Repräsentantensystem für die Äquivalenzrelation, wenn es für jede Äquivalenzklasse genau ein Element aus ${}T$ aus dieser Klasse gibt.
4. Zu einem Graphen nennt man

   ${}\Delta (G)={\max {\left(d(v),v\in V\right)}}\,$

   den Maximalgrad des Graphen.

5. Ein Wald ist ein Graph ohne Kreis.
6. Die minimale Anzahl von Knoten in einer Knotenüberdeckung von ${}G$ heißt Knotenüberdeckungszahl von ${}G$.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Die Siebformel.
2. Der Isomorphiesatz für endliche boolesche Verbände.
3. Der Satz von König für einen bipartiten Graphen.

Lösung

1. Es sei ${}G$ eine Menge und es seien ${}A_{i}\subseteq G$, ${}i=1,\ldots ,n$, endliche Teilmengen. Für eine Teilmenge ${}J\subseteq {\{1,\ldots ,n\}}$ sei

   ${}A_{J}=\bigcap _{i\in J}A_{i}\,.$

   Dann ist

   ${}{\#\left(\bigcup _{i=1}^{n}A_{i}\right)}=\sum _{k=1}^{n}(-1)^{k+1}{\left(\sum _{J\subseteq \{1,\ldots ,n\},\,{\#\left(J\right)}=k}{\#\left(A_{J}\right)}\right)}\,.$

2. Jeder endliche boolesche Verband ${}B$ ist isomorph zur Potenzmenge einer endlichen Menge.
3. In einem bipartiten Graphen stimmt die Paarungszahl mit der Knotenüberdeckungszahl überein.

Aufgabe (2 Punkte)

Vor einem Fußballspiel begrüßt jeder der elf Spieler einer Mannschaft jeden Spieler der anderen Mannschaft, jeder Spieler begrüßt die vier Unparteiischen und diese begrüßen sich alle untereinander. Wie viele Begrüßungen finden statt?

Lösung

Die Anzahl der Begrüßungen ist

${}11\cdot 11+2\cdot 11\cdot 4+{\binom {4}{2}}=121+88+6=215\,.$

Aufgabe (5 (1+3+1) Punkte)

Zu je zwei Punkten in der Produktmenge ${}\mathbb {Q} ^{2}$ gibt es eine Verbindungsgerade und einen Mittelpunkt, der die Verbindungsstrecke halbiert.

1. Man gebe zu zwei Punkten ${}(a_{1},a_{2})$ und ${}(b_{1},b_{2})$ die Koordinaten des Mittelpunktes an.
2. Es seien in der Produktmenge ${}\mathbb {Z} ^{2}$ fünf Punkte gegeben (jeder Punkt habe also ganzzahlige Koordinaten). Zeige, dass mindestens einer der Mittelpunkte ganzzahlige Koordinaten haben muss.
3. Gilt die Eigenschaft aus (2) auch bei vier Punkten?

Lösung

1. Der Mittelpunkt von ${}(a_{1},a_{2})$ und ${}(b_{1},b_{2})$ besitzt die Koordinaten ${}\left({\frac {a_{1}+b_{1}}{2}},\,{\frac {a_{2}+b_{2}}{2}}\right)$.
2. Wir betrachten für jeden Punkt, ob die Koordinaten gerade oder ungerade sind. Dafür gibt es vier Möglichkeiten ($(g,g),\,(g,u),\,(u,g)\,(u,u)$). Da es ${}5$ Punkte gibt, kommt eine dieser Möglichkeiten zumindest zweimal vor. Seien ${}P$ und ${}Q$ zwei Punkte, die hinsichtlich dieser Eigenschaft übereinstimmen. Da das arithmetische Mittel von zwei geraden Zahlen und von zwei ungeraden Zahlen ganzzahlig ist, besitzt der Mittelpunkt von ${}P$ und ${}Q$ ganzzahlige Koordinaten.
3. Die vier Punkte

   $(0,0),\,(0,1),\,(1,0)\,,(1,1)$

   zeigen, dass dies nicht gelten muss.

Aufgabe (5 Punkte)

Beweise den binomischen Lehrsatz für einen kommutativen Halbring ${}R$.

Lösung

Es seien ${}a,b\in R$. Wir führen Induktion nach ${}n$. Für ${}n=0$ steht einerseits ${}(a+b)^{0}=1$ und andererseits ${}a^{0}b^{0}=1$. Es sei die Aussage bereits für ${}n$ bewiesen. Dann ist

${}{\begin{aligned}(a+b)^{n+1}&=(a+b)(a+b)^{n}\\&=(a+b){\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)}\\&=a\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)+b\left(\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k}\right)\\&=\sum _{k=0}^{n}{\binom {n}{k}}a^{k+1}b^{n-k}+\sum _{k=0}^{n}{\binom {n}{k}}a^{k}b^{n-k+1}\\&=\sum _{k=1}^{n+1}{\binom {n}{k-1}}a^{k}b^{n-k+1}+\sum _{k=0}^{n+1}{\binom {n}{k}}a^{k}b^{n-k+1}\\&=\sum _{k=1}^{n+1}\left({\binom {n}{k-1}}+{\binom {n}{k}}\right)a^{k}b^{n+1-k}+b^{n+1}\\&=\sum _{k=1}^{n+1}{\binom {n+1}{k}}a^{k}b^{n+1-k}+b^{n+1}\\&=\sum _{k=0}^{n+1}{\binom {n+1}{k}}a^{k}b^{n+1-k}.\end{aligned}}$

Aufgabe (2 Punkte)

Es sei ${}M=\{a,b\}$ eine zweielementige Menge. Beschreibe vollständig (durch Auflistung aller zugehörigen Paare) die Relation auf der Potenzmenge ${}{\mathfrak {P}}\,(M)$, die durch die Teilmengenbeziehung gegeben ist.

Lösung

Die Potenzmenge besteht aus den Elementen

$\emptyset ,\{a\},\{b\},\{a,b\}.$

Eine vollständige Auflistung aller Teilmengenbeziehungen ist

$(\emptyset ,\emptyset ),\,(\emptyset ,\{a\}),\,(\emptyset ,\{b\}),\,(\emptyset ,\{a,b\}),\,(\{a\},\{a\}),\,(\{a\},\{a,b\}),\,(\{b\},\{b\}),\,(\{b\},\{a,b\}),\,(\{a,b\},\{a,b\}).$

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

Wir betrachten das Spiel Schnick Schnack Schnuck mit den Objekten Schere, Stein, Papier und Brunnen als eine Gewinnrelation.

1. Skizziere diese Gewinnrelation durch einen gerichteten Graphen (Pfeildiagramm).
2. Ist die Gewinnrelation transitiv?
3. Gibt es eine dreielementige Teilmenge der Objekte derart, dass die darauf eingeschränkte Relation transitiv ist?

Lösung

1. ${}\,$
2. Stein schlägt Schere und Schere schlägt Papier, aber Stein schlägt nicht Papier, also ist die Relation nicht transitiv.
3. Die Relation eingeschränkt auf die Teilmenge bestehend aus Papier, Brunnen und Stein ist transitiv (in der angegebenen Reihenfolge wird geschlagen).

Aufgabe (0 Punkte)

Lösung /Aufgabe/Lösung

Aufgabe (7 Punkte)

Beweise den Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.

Lösung

Wir setzen ${}B=\{1,\ldots ,k\}$. Zu ${}j=1,\ldots ,k$ setzen wir

${}F_{j}={\left\{f:A\rightarrow B\mid j{\text{ wird nicht getroffen unter }}f\right\}}\,.$

Die Menge der nichtsurjektiven Abbildungen ist somit ${}F=\bigcup _{j=1}^{k}F_{j}$. Zu ${}C\subseteq B$ haben die Durchschnitte

${}F_{C}=\bigcap _{j\in C}F_{j}\,$

eine inhaltliche Bedeutung: Es handelt sich um alle Funktionen von ${}A$ nach ${}B\setminus C$. Deren Anzahl ist nach Satz 2.2 (Diskrete Mathematik (Osnabrück 2020)) gleich ${}(k-j)^{n}$. Nach der Siebformel ist somit

${}{\begin{aligned}{\#\left(F\right)}&=\sum _{j=1}^{k}(-1)^{j+1}{\left(\sum _{C\subseteq \{1,\ldots ,k\},\,{\#\left(C\right)}=j}{\#\left(F_{C}\right)}\right)}\\&=\sum _{j=1}^{k}(-1)^{j+1}{\binom {k}{j}}(k-j)^{n}\\&=\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}$

Die Anzahl der surjektiven Abbildungen ist daher gleich

${}{\begin{aligned}k^{n}-{\left(\sum _{\ell =0}^{k-1}(-1)^{k-\ell +1}{\binom {k}{\ell }}\ell ^{n}\right)}&=k^{n}+\sum _{\ell =0}^{k-1}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}\\&=\sum _{\ell =0}^{k}(-1)^{k-\ell }{\binom {k}{\ell }}\ell ^{n}.\end{aligned}}$

Aufgabe (3 Punkte)

Zeige, dass auf der Funktionenmenge ${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ Infima und Suprema existieren und dass somit ${}M$ ein Verband ist. Skizziere das Infimum von der Sinusfunktion und der Kosinusfunktion.

Lösung

Zu Funktionen ${}f,g\in \operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ kann man direkt die Funktion

${}{\operatorname {sup} \,(f,g)}(x):={\operatorname {sup} \,(f(x),g(x))}\,$

punktweise definieren. Dabei gilt offenbar

${}h\geq {\operatorname {sup} \,(f,g)}\,$

für jede Funktion ${}h$, die sowohl ${}h\geq f$ als auch ${}h\geq g$ erfüllt. Es handelt sich also wirklich um das ordnungstheoretische Supremum. Ebenso für das Infimum.

Aufgabe (6 (2+2+2) Punkte)

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Relation auf ${}M$, die reflexiv und transitiv sei.

1. Zeige, dass auf ${}M$ durch ${}x\sim y$, falls ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ ist, eine Äquivalenzrelation definiert wird.
2. Es sei ${}Q$ die Quotientenmenge zu ${}M$ zur Äquivalenzrelation aus (1). Zeige, dass durch ${}[x]\leq [y]$, falls ${}x\preccurlyeq y$, eine wohldefinierte Relation auf ${}Q$ gegeben ist.
3. Zeige, dass die Relation auf ${}Q$ aus (2) eine Ordnungsrelation ist.

Lösung

1. Die Reflexivität ist klar. Zur Symmetrie: Sei ${}x\sim y$, also ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$. Somit gilt auch ${}y\sim x$. Zur Transitivität: Sei ${}x\sim y$ und ${}y\sim z$. Dies bedeutet ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ und ${}y\preccurlyeq z$ und ${}z\preccurlyeq y$. Die Transitivität von ${}\preccurlyeq$ liefert ${}x\preccurlyeq z$ und ${}z\preccurlyeq x$. Dies bedeutet ${}x\sim z$.
2. Es sei ${}[x]=[u]$ und ${}[y]=[v]$ und es gelte ${}x\preccurlyeq y$. Da ${}u$ zu ${}x$ und ${}v$ zu ${}y$ äquivalent sind, gilt insbesondere ${}u\preccurlyeq x$ und ${}y\preccurlyeq v$. Eine doppelte Anwendung der Transitivität von ${}\preccurlyeq$ liefert ${}u\preccurlyeq v$, was die Wohldefiniertheit besagt.
3. Nach Definition von ${}\leq$ auf ${}Q$ gilt ${}[x]\leq [y]$ genau dann, wenn ${}x\preccurlyeq y$ gilt. Somit ergibt sich die Reflexivität und die Transitivität von ${}\leq$ unmittelbar aus den entsprechenden Eigenschaften von ${}\preccurlyeq$. Zur Antisymmetrie: Sei ${}[x]\leq [y]$ und ${}[y]\leq [x]$. Dies bedeutet ${}x\preccurlyeq y$ und ${}y\preccurlyeq x$, was wiederum ${}x\sim y$, also ${}[x]=[y]$, bedeutet.

Aufgabe (2 Punkte)

Skizziere den Teilerfremdheitsgraphen zu den Zahlen

$1,2,3,4,6,8,9,12.$

Lösung

Aufgabe (3 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Diamantgraphen.

Lösung

Wir bezeichnen die Punkte im Uhrzeigersinn von oben mit ${}1,2,3,4$. Die Punkte ${}1$ und ${}3$ haben den Grad ${}3$, die beiden anderen Punkte den Grad ${}2$. Diese können nicht durch einen Automorphismus ineinander überführt werden. Allerdings können ${}1$ und ${}3$ und ${}2$ und ${}4$ untereinander vertauscht werden. und diese beiden Vertauschungen sind unabhängig voneinander. Deshalb ist die Automorphismengruppe gleich ${}\mathbb {Z} /(2)\times \mathbb {Z} /(2)$.

Aufgabe (4 Punkte)

Bestimme die Anzahl der Spannbäume des vollständigen Graphen zu ${}4$ Punkten mit Hilfe des Satzes von Kirchhoff.

Lösung

Die Adjazenzmatrix gleich

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

und die Gradmatrix ist

${\begin{pmatrix}3&0&0&0\\0&3&0&0\\0&0&3&0\\0&0&0&3\end{pmatrix}},$

somit ist die Laplace-Matrix gleich

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

Wenn man die erste Zeile und die erste Spalte streicht, so erhält man

${\begin{pmatrix}3&-1&-1\\-1&3&-1\\-1&-1&3\end{pmatrix}}.$

Deren Determinante ist

${}3(9-1)+(-3-1)-1(1+3)=24-4-4=16\,$

die Anzahl der Spannbäume ist also ${}16$.

Aufgabe (6 Punkte)

Beweise den Charakterisierungssatz für bipartite Graphen mittels Kreisen.

Lösung

Es sei ${}V=A\uplus B$ eine bipartite Zerlegung eines bipartiten Graphen. In jedem Weg in einem bipartiten Graphen gehören die Knoten abwechselnd zu ${}A$ oder zu ${}B$. Die Existenz eines Kreises mit ungerader Anzahl führt daher direkt zu einem Widerspruch.

Es sei nun umgekehrt die Kreisbedingung erfüllt. Wir können annehmen, dass ${}G$ zusammenhängend ist. Es sei ${}v\in V$ ein fixierter Punkt. Wir definieren

${}A={\left\{x\in V\mid {\text{ es gibt einen geradzahligen Weg von }}v{\text{ nach }}x\right\}}\,$

und

${}B={\left\{x\in V\mid {\text{ es gibt einen ungeradzahligen Weg von }}v{\text{ nach }}x\right\}}\,.$

Wegen der Zusammenhangseigenschaft ist

${}V=A\cup B\,.$

Nehmen wir an, dass ${}A$ und ${}B$ nicht disjunkt sind, sagen wir ${}y\in A\cap B$. Es gibt dann Wege

${}v=v_{0}\sim v_{1}\sim \ldots \sim v_{r}=y\,$

und

${}v=v_{0}\sim u_{1}\sim \ldots \sim u_{s}=y\,$

mit ${}r$ gerade und ${}s$ ungerade. Indem man die beiden Wege zusammensetzt, erhält man einen Zyklus mit ungerade vielen Knoten. Wenn es in ihm Wiederholungen gibt, so kann man daraus zwei kleinere Zyklen herausarbeiten, von denen einer ebenfalls eine ungerade Anzahl besitzt. Somit erhält man auch einen ungeraden Kreis im Widerspruch zur Voraussetzung. Die beiden Mengen sind also disjunkt. Wenn es eine Kante innerhalb von ${}A$ geben würde, so würden die daran beteiligten Punkte sofort auch zu ${}B$ gehören im Widerspruch zur gezeigten Disjunktheit.

Aufgabe (9 (1+1+2+5) Punkte)

Wir betrachten Graphen

${}G=S(n_{1},n_{2},\ldots ,n_{k})\,$

von der folgenden Bauart: Es gibt ein Zentrum ${}z$, an das ${}k$ lineare Graphen (Strahlen) der Länge ${}n_{1},n_{2},\ldots ,n_{k}$ anliegen. Ansonsten gibt es keine weiteren Kanten.

1. Skizziere einen solchen Graphen für ${}k=5$ und

   ${}(n_{1},n_{2},n_{3},n_{4},n_{5})=(2,3,1,3,4)\,.$

2. Erstelle eine Formel für die Anzahl der Knoten und die Anzahl der Kanten von ${}G$.
3. Beschreibe eine minimale Knotenüberdeckung von ${}G$, die ${}z$ enthält, und eine minimale Knotenüberdeckung, die ${}z$ nicht enthält.
4. Bestimme die Knotenüberdeckungszahl von ${}G$.

Lösung

1. ${}\,$

   

2. Die Anzahl der Kanten ist ${}\sum _{j=1}^{k}n_{j}$ und die Anzahl der Knoten ist ${}1+\sum _{j=1}^{k}n_{j}$.
3. Wir betrachten ${}z$ als Nullpunkt und nennen einen Punkt des Graphen gerade, wenn sein Abstand zum Nullpunkt gerade ist, andernfalls ungerade. Dann bilden alle geraden Punkte eine minimale Knotenüberdeckung, an der ${}z$ beteiligt ist. Ebenso bilden alle ungeraden Punkte eine minimale Knotenüberdeckung, an der ${}z$ nicht beteiligt ist.
4. Wenn ${}z$ zu einer Knotenüberdeckung gehört, so sind die daran direkt anliegenden Kanten auf den Strahlen abgedeckt. Man muss dann noch auf den einzelnen Strahlen die jeweils verbleibenden Kanten ${}\{1,2\},\{2,3\},\{3,4\},\ldots ,\{n_{j-1},n_{j}\}$ abdecken. Dazu braucht man minimal ${}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor$ Punkte. Eine minimale Knotenüberdeckung, die ${}z$ enthält, braucht also ${}1+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor$ Knoten, und solche Überdeckungen gibt es wegen (3). Wenn ${}z$ nicht zu einer Knotenüberdeckung gehört, so muss diese den ersten Punkt auf jedem einzelnen Strahlen enthalten (um die Kante ${}\{z,1\}$) abzudecken. Weiter müssen auf jedem Strahl die Kanten ${}\{2,3\},\{3,4\},\ldots ,\{n_{j-1},n_{j}\}$ abgedeckt sein, wozu man minimal ${}\left\lfloor {\frac {n_{j}-1}{2}}\right\rfloor$ Punkte braucht. Eine minimale Knotenüberdeckung, die ${}z$ nicht enthält, braucht also

   ${}k+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}-1}{2}}\right\rfloor =\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}+1}{2}}\right\rfloor \,$

   Knoten, und solche Überdeckungen gibt es wegen (3).

   Es geht also um das Minimum dieser beiden Zahlen. Wenn alle ${}n_{j}$ gerade sind, so ist die Knotenüberdeckungszahl gleich

   $\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}+1}{2}}\right\rfloor ,$

   wenn ein ${}n_{j}$ ungerade sind, so ist die Knotenüberdeckungszahl gleich

   $1+\sum _{j=1}^{k}\left\lfloor {\frac {n_{j}}{2}}\right\rfloor .$