Kurs:Diskrete Mathematik/15/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	2	4	4	6	0	7	0	4	2	0	0	0	0	0	10	0	0	45

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Kommutativität einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M.$

2. Ein Atom  ${}a\in M$  in einer geordneten Menge ${}(M,\preccurlyeq )$ mit einem kleinsten Element ${}0$.
3. Ein Ideal ${}{\mathfrak {a}}\subseteq R$ in einem kommutativen Ring ${}R$.
4. Zwei isomorphe Graphen  ${}G=(V,E)$  und  ${}H=(W,F)$. 
5. Der Quotientengraph zu einer Äquivalenzrelation ${}\sim$ auf einem Graphen  ${}G=(V,E)$. 
6. Eine maximale Paarung  ${}P\subseteq E$  in einem Graphen  ${}G=(V,E)$. 

Lösung

1. Eine Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

   heißt kommutativ, wenn für alle ${}x,y\in M$ die Gleichheit

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

   gilt.

2. Ein Element  ${}a\in M$  heißt Atom, wenn  ${}a\neq 0$  ist und die Beziehung  ${}x\preccurlyeq a$  nur für  ${}x=0$  und  ${}x=a$  gilt.
3. Ein Ideal ist eine nichtleere Teilmenge ${}{\mathfrak {a}}\subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
   1. Für alle ${}a,b\in {\mathfrak {a}}$ ist auch ${}a+b\in {\mathfrak {a}}$.
   2. Für alle ${}a\in {\mathfrak {a}}$ und ${}r\in R$ ist auch ${}ra\in {\mathfrak {a}}$.
4. Die beiden Graphen  ${}G=(V,E)$  und  ${}H=(W,F)$  heißen isomorph, wenn es einen Graphisomorphismus ${}\varphi \colon G\rightarrow H$ gibt.
5. Der Quotientengraph ist die Quotientenmenge ${}V/\sim$, versehen mit der Bildgraphenstruktur zur kanonischen Abbildung

   $V\longrightarrow V/\sim .$

6. Die Paarung  ${}P\subseteq E$  heißt maximal, wenn jedes ${}P'$ mit  ${}P\subset P'\subseteq E$  keine Paarung ist.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die atomare Darstellung in einem booleschen Verband.
2. Der Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.
3. Der Satz über die Potenzen der Adjazenzmatrix.

Lösung

1. In einem endlichen booleschen Verband besitzt jedes Element  ${}x\in B$  eine eindeutige Darstellung der Form

   ${}x=a_{1}\sqcup \ldots \sqcup a_{n}\,$

   mit Atomen

   ${}a_{j}$.
2. Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge. Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

   $\sum _{j=0}^{k}(-1)^{k-j}{\binom {k}{j}}j^{n}.$

3. Es sei  ${}G=(V,E)$  ein Graph mit zugehöriger Adjazenzmatrix ${}A$. Dann ist die Anzahl der Wege von ${}u$ nach ${}v$ der Länge ${}\ell$ gleich dem Eintrag an der Stelle ${}(u,v)$ zur Matrixpotenz ${}A^{\ell }$.

Aufgabe (2 Punkte)

Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?

Lösung

1. Leere Mulde auf dem Straßenplatz ${}A$ abladen.
2. Volle Mulde auf Fahrzeug hochladen.
3. Volle Mulde auf dem Straßenplatz ${}B$ abladen.
4. Leere Mulde auf Fahrzeug hochladen.
5. Leere Mulde auf den Garagenvorplatz abladen.
6. Volle Mulde auf Fahrzeug hochladen.

Es sind also sechs Ladevorgänge nötig.

Aufgabe (4 Punkte)

Es sei ${}M$ eine ${}n$-elementige Menge. Zeige durch Induktion über ${}k$, dass die Anzahl der ${}k$-elementigen Teilmengen von ${}M$ gleich dem Binomialkoeffizienten

${\binom {n}{k}}$

ist.

Lösung

Es sei ${}n$ fixiert. Bei  ${}k=0$  gibt es nur die leere Menge, was mit dem Binomialkoeffizienten

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

übereinstimmt. Es sei die Aussage also für ein ${}k$ zwischen ${}0$ und ${}n-1$ schon bewiesen. Jeder ${}k$-elementigen Teilmenge ${}S$ von ${}M$ und jedem der ${}n-k$ Elemente ${}x$ aus ${}M\setminus S$ kann man die ${}k+1$-elementige Menge

${}T=S\cup \{x\}\,$

zuordnen. Dabei wird jede ${}k+1$-elementige Menge ${}T$ erreicht, und zwar ${}k+1$-fach, da man ja aus ${}T$ jedes der ${}k+1$ Elemente herausnehmen kann. Zwischen der Anzahl ${}A_{k}$ der ${}k$-elementigen Teilmengen von ${}M$ und der Anzahl ${}A_{k+1}$ der ${}k+1$-elementigen Teilmengen von ${}M$ besteht also der Zusammenhang

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

Unter Verwendung der Induktionsvoraussetzung ist daher

${}{\begin{aligned}A_{k+1}&={\frac {n-k}{k+1}}A_{k}\\&={\frac {n-k}{k+1}}{\binom {n}{k}}\\&={\frac {n-k}{k+1}}\cdot {\frac {n(n-1)\cdots (n-k+1)}{k!}}\\&={\frac {n(n-1)\cdots (n-k+1)(n-k)}{(k+1)!}}\\&={\binom {n}{k+1}}\end{aligned}}$

Aufgabe (4 Punkte)

Es sei ${}M$ eine beliebige Menge. Zeige, dass es keine surjektive Abbildung von ${}M$ in die Potenzmenge ${}{\mathfrak {P}}\,(M)$ geben kann.

Lösung

Wir nehmen an, dass es eine surjektive Abbildung

$F\colon M\longrightarrow {\mathfrak {P}}\,(M),\,x\longmapsto F(x),$

gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir

${}T={\left\{x\in M\mid x\notin F(x)\right\}}\,.$

Da dies eine Teilmenge von ${}M$ ist, muss es wegen der Surjektivität ein  ${}y\in M$  geben mit

${}F(y)=T\,.$

Es gibt nun zwei Fälle, nämlich ${}y\in F(y)$ oder ${}y\not \in F(y)$. Im ersten Fall ist also  ${}y\in T$,  und damit, nach der Definition von ${}T$, auch  ${}y\notin F(y)$,  Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von ${}T$,  ${}y\in T$,  und das ist ebenfalls ein Widerspruch.

Aufgabe (6 (3+3) Punkte)

Wir betrachten eine Rekursionsvorschrift, die zu einen Zahlendreieck (analog zum Pascalschen Dreieck) führt. In der ersten Zeile steht zentral die ${}256$, links und rechts davon stehen unendlich viele ${}1$ (die nicht aufgeführt werden müssen). Die jeweils nächste Zeile entsteht, indem man von zwei benachbarten Zahlen der Vorgängerzeile das geometrische Mittel nimmt und das Ergebnis darunter in der neuen Zeile platziert.

1. Bestimme die ersten Zeilen dieses Zahlendreiecks, bis sämtliche Einträge kleiner als ${}6$ sind.
2. Welche Eigenschaft gilt in jeder Zeile? Warum?

Lösung

1. Es ergibt sich das folgende Schema.

   ${\begin{matrix}&&&&&256&&&&&\\&&&&16&&16&&&&\\&&&4&&16&&4&&\\&&2&&8&&8&&2&&\\&{\sqrt {2}}&&4&&8&&4&&{\sqrt {2}}&\\2^{1/4}&&2\cdot 2^{1/4}&&4{\sqrt {2}}&&4{\sqrt {2}}&&2\cdot 2^{1/4}&&2^{1/4}\end{matrix}}$

   Wegen

   ${}(4{\sqrt {2}})^{2}=32\leq 6^{2}\,$

   sind wir fertig.

2. In jeder Zeile ist das Produkt über alle Zahlen gleich ${}256$. Dies beweist man durch Induktion über den Zeilenindex. In der Startzeile ist das richtig (die nicht hingeschriebenen Zahlen sind ${}1$). Es sei also das Produkt der Zahlen in einer Zeile gleich ${}256$. Jede Zahl dieser Zeile geht zweifach in die folgende Zeile ein, einmal als Beitrag zum geometrischen Mittel mit der linken Zahl und einmal als Beitrag zum geometrischen Mittel mit der rechten Zahl. Dabei geht wegen  ${}{\sqrt {ab}}={\sqrt {a}}{\sqrt {b}}$  jeweils die Quadratwurzel ein. Das Gesamtprodukt bleibt dabei erhalten.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (7 Punkte)

Beweise das allgemeine Distributivgesetz für einen kommutativen Halbring.

Lösung

Wir machen eine Doppelinduktion nach ${}r$ und nach ${}s$. D.h. wir beweisen die Aussage für jedes feste ${}r$ durch Induktion nach ${}s$ (innere Induktion) und erhöhen dann in einem eigenen Induktionsdurchgang ${}r$ (äußere Induktion). Bei  ${}r=0$  ist nichts zu zeigen, da dann die Summen links und rechts leer sind, also gleich ${}0$. Es sei also  ${}r=1$,  sodass der linke Faktor einfach eine fixierte Zahl  ${}a=a_{1}$  ist. Wir wollen die Aussage in dieser Situation für beliebiges ${}s$ zeigen. Bei  ${}s=0,1$  ist die Aussage klar. Es sei die Aussage nun für ein

${}s\geq 2\,$

schon bewiesen. Dann ist

${}{\begin{aligned}a\cdot {\left(b_{1}+\cdots +b_{s}+b_{s+1}\right)}&=a\cdot {\left({\left(b_{1}+\cdots +b_{s}\right)}+b_{s+1}\right)}\\&=a\cdot {\left(b_{1}+\cdots +b_{s}\right)}+ab_{s+1}\\&={\left(\sum _{k=1}^{s}ab_{k}\right)}+ab_{s+1}\\&=\sum _{k=1}^{s+1}ab_{k}\end{aligned}}$

nach dem Distributivgesetz und der Induktionsvoraussetzung.

Es sei die Aussage nun für ein festes ${}r$ und jedes ${}s$ bewiesen. Dann ist wieder mit dem Distributivgesetz und der Induktionsvoraussetzung

${}{\begin{aligned}{\left(\sum _{i=1}^{r+1}a_{i}\right)}\cdot {\left(\sum _{k=1}^{s}b_{k}\right)}&={\left({\left(\sum _{i=1}^{r}a_{i}\right)}+a_{r+1}\right)}\cdot {\left(\sum _{k=1}^{s}b_{k}\right)}\\&={\left(\sum _{i=1}^{r}a_{i}\right)}\cdot {\left(\sum _{k=1}^{s}b_{k}\right)}+a_{r+1}\cdot {\left(\sum _{k=1}^{s}b_{k}\right)}\\&=\sum _{1\leq i\leq r,\,1\leq k\leq s}a_{i}b_{k}+\sum _{k=1}^{s}a_{r+1}b_{k}\\&=\sum _{1\leq i\leq r+1,\,1\leq k\leq s}a_{i}b_{k}.\end{aligned}}$

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (4 Punkte)

Zeige, dass es zu ganzen Zahlen ${}d,n$ mit ${}d>0$ eindeutig bestimmte ganze Zahlen ${}k,s$ mit

${}n=kd+s\,$

und mit

${}-{\frac {d}{2}}<s\leq {\frac {d}{2}}\,$

gibt.

Lösung

Aufgrund der Division mit Rest in ${}\mathbb {Z}$ gibt es eindeutig bestimmte ganze Zahlen ${}q$ und ${}r$ mit

${}0\leq r<d\,$

mit

${}n=qd+r\,.$

Bei

${}r\leq {\frac {d}{2}}\,$

ist die Existenz bewiesen. Bei

${}r>{\frac {d}{2}}\,$

setzt man

${}s:=r-d\,.$

Es ist dann

${}0>s=r-d>{\frac {d}{2}}-d=-{\frac {d}{2}}\,$

und

${}n=qd+r=(q+1)d+r-d=(q+1)d+s\,$

ergibt die Existenz. Aus zwei Darstellungen

${}kd+s=n=\ell d+t\,$

mit  ${}s\geq t$  ergibt sich

${}0=(k-\ell )d+s-t\,$

mit

${}0\leq s-t<d\,$

und die Eindeutigkeit in der Division mit Rest sichert die Eindeutigkeit in der vorliegenden Form.

Aufgabe (2 Punkte)

Zeige, dass die Relation auf ${}\mathbb {N} \times \mathbb {N}$, die durch

$(a,b)\sim (c,d),{\text{ falls }}a+d=b+c,$

festgelegt ist, eine Äquivalenzrelation ist.

Lösung

1. Wegen  ${}a+b=b+a$  ist  ${}(a,b)\sim (a,b)$,  die Relation ist also reflexiv.
2. Die Symmetrie folgt daraus, dass aus  ${}a+d=b+c$  sofort  ${}c+b=d+a$  folgt.
3. Zum Nachweis der Transitivität sei ${}(a,b)\sim (c,d)$ und ${}(c,d)\sim (e,f)$, also  ${}a+d=b+c$  und  ${}c+f=d+e$.  Dann ist

   ${}a+f+c=a+d+e=b+e+c\,.$

   Aufgrund der Abziehregel ist dann

   ${}a+f=b+e\,,$

   und dies bedeutet  ${}(a,b)\sim (e,f)$. 

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (10 Punkte)

Beweise den Charakterisierungssatz für eulersche Graphen.

Lösung

Von (1) nach (2) ist klar, da bei einen geschlossenen Eulerzug jeder Knotenpunkt genau so oft besucht wie verlassen wird.

Von (2) nach (3). Wir führen Induktion über die Anzahl der Kanten. Da der Graph zusammenhängend ist, handelt es sich um einen isolierten Punkt oder aber jeder Knoten besitzt einen Grad von zumindest ${}2$. Deshalb muss es in ${}G$ einen Kreis ${}K$ geben. Man kann ja inn einem beliebigen Punkt starten und von diesem Punkt ausgehend nach und nach einen Kantenzug konstruieren. Wenn der Kantenzug in einen Punkt hineingeht, so kann man den Kantenzug fortsetzen, da zumindest zwei Kanten in dem Punkt zusammenlaufen. Wenn erstmal ein schon erreichter Punkt erneut auftaucht, ist der Kreis fertig, die „Vorperiode“ kann man außer Acht lassen. Es seien ${}F$ die Kanten des Kreises und wir betrachten den neuen Graphen  ${}G'=(V,E\setminus F)$.  Wenn ein Punkt aus ${}V$ zu einer Kante aus ${}F$ inzident ist, so reduziert sich der Grad in diesem Knoten um ${}2$, da ja jeder Punkt in einem Kreis inzident zu zwei Kanten ist. Wenn ein Punkt im Kreis nicht aufgerufen wird, so ändert sich der Grad nicht. In jedem Fall besitzt in ${}G'$ jeder Punkt wieder einen geraden Grad. Der neue Graph muss nicht mehr zusammenhängend sein, allerdings erfüllen die einzelnen Zusammenhangskomponenten von ${}G'$ wieder die Voraussetzung, dass sämtliche Grade gerade sind. Nach Induktionsvoraussetzung besitzen die Zusammenhangskomponenten jeweils eine Darstellung als Vereinigung mit kantendisjunkten Kreisen. Also besitzt ${}G'$ eine Darstellung als Vereinigung mit kantendisjunkten Kreisen und zusammen mit ${}K$ ergibt sich eine Darstellung von ${}G$ als Vereinigung mit kantendisjunkten Kreisen.

Von (3) nach (1). Es seien  ${}K_{j}=(V_{j},E_{j})$,   ${}j\in J$,  die beteiligten kantendisjunkten Kreise, die ${}G$ überdecken. Wir konstruieren induktiv Kantenzüge, die für zunehmend größere Vereinigungen dieser Kreise einen Eulerzug darstellen. Einen einzelnen Kreis kann man unmittelbar als einen Eulerzug für diesen Kreis auffassen. Es sei nun vorausgesetzt, dass man ${}s$ Kreise, die wir als ${}K_{1},\ldots ,K_{s}$ durchnummerieren, derart gefunden hat, dass es einen Eulerzug für

${}G_{s}=\bigcup _{j=1}^{s}K_{j}\,$

gibt. Bei  ${}s<r$  gibt es aufgrund des Zusammenhangs des Graphen einen weiteren Kreis, den wir ${}K_{s+1}$ nennen, der einen gemeinsamen Knotenpunkt mit ${}G_{s}$ hat, sagen wir ${}u$. Dann erhält man aus dem Eulerzug für ${}G_{s}$ einen Eulerzug für  ${}G_{s+1}=G_{s}\cup K_{s+1}$,  indem man, wenn der Eulerzug den Punkt ${}u$ erreicht, in den Kreis ${}K_{s+1}$ abbiegt, diesen einmal durchläuft und danach an der Stelle ${}u$ den alten Eulerzug fortsetzt. Da ${}K_{s+1}$ kantendisjunkt zu ${}G_{s}$ ist, entsteht dabei wieder ein Eulerzug.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen