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

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	$\sum$
Punkte	3	3	1	2	3	6	3	1	6	7	2	4	8	5	4	1	3	2	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine linkseindeutige Relation  $R\subseteq M\times N$. 
2. Ein boolescher Verband $M$.
3. Eine Äquivalenzrelation $\sim$ auf einer Menge $M$.
4. Ein aufspannender Wald eines Graphen  $G=(V,E)$. 
5. Ein bipartiter Graph  $G=(V,E)$. 
6. Eine Paarung  $P\subseteq E$  in einem Graphen  $G=(V,E)$  für eine Teilmenge  $S\subseteq V$. 

Lösung

1. Die Relation  $R\subseteq M\times N$  heißt linkseindeutig, wenn es zu jedem  $y\in N$  maximal ein  $x\in M$  mit  $(x,y)\in R$  gibt.
2. Ein Verband $M$ heißt boolesch, wenn er komplementär und distributiv ist.
3. Eine Äquivalenzrelation $\sim$ auf einer Menge $M$ ist eine Relation, die die folgenden drei Eigenschaften besitzt (für beliebige $x,y,z\in M$).
   1. $x\sim x$.
   2. Aus $x\sim y$ folgt $y\sim x$.
   3. Aus $x\sim y$ und $y\sim z$ folgt $x\sim z$.
4. Ein aufspannender Wald ist ein Untergraph  $W\subseteq G$,  der ein Wald ist, dessen Bäume mit den Zusammenhangskomponenten von $V$ übereinstimmen.
5. Ein Graph heißt bipartit, wenn es eine disjunkte Zerlegung

   $V=A\uplus B$

   derart gibt, dass es nur Kanten zwischen $A$ und $B$ gibt.

6. Eine Paarung für $S$ liegt vor, wenn jeder Knoten aus $S$ von einer Kante aus $P$ abgedeckt wird.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl der surjektiven Abbildungen und Stirling-Zahlen zweiter Art.
2. Der Satz über die Charakterisierung von isomorphen Abbildungen zwischen endlichen Mengen.
3. Der Faktorisierungssatz für einen Graphhomomorphismus.

Lösung

1. 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 $k!S(n,k)$.
2. Es seien $f_1:L_1\to M_1$ und $f_2:L_2\to M_2$ Abbildungen zwischen endlichen Mengen. Dann sind $f_1$ und $f_2$ genau dann zueinander isomorph, wenn ihre Faseranzahltupel übereinstimmen.
3. Es sei $\phi :G\to H$ ein schwacher Homomorphismus zwischen den Graphen  $G=(V,E)$  und  $H=(W,F)$.  Dann gibt es eine Faktorisierung von $\phi$ als

   $G\stackrel{q}{⟶}G/\sim \stackrel{r}{⟶}(U,K)\stackrel{s}{⟶}(U,K^{\prime })\stackrel{t}{⟶}(W,F),$

   wobei $q$ die Quotientenabbildung zu einer Äquivalenzrelation auf $V$ ist, $r$ ein Isomorphismus ist, $s$ einen knotenidentischen Untergraphen und $t$ einen vollen Untergraphen

   beschreibt.

Aufgabe (1 Punkt)

Es seien $a,b$ Elemente in einem kommutativen Halbring $R$. Berechne

$(a+2b)\cdot (2a+3b).$

Lösung

Nach dem Distributivgesetz ist

$\begin{array}{cc}(a+2b)\cdot (2a+3b)& =a\cdot (2a+3b)+2b\cdot (2a+3b)\\ & =2a^2+3ab+4ab+6b^2\\ & =2a^2+7ab+6b^2.\end{array}$

Aufgabe (2 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von $10$ Cent begleichen?

Lösung

Wir zählen zunächst die Möglichkeiten, mit den $5$- und $10$-Centmünzen die folgenden Beträge darzustellen:

$0\text{ Cent}:1\text{ Möglichkeit},$

$5\text{ Cent}:1\text{ Möglichkeit},$

$10\text{ Cent}:2\text{ Möglichkeiten}.$

Dann betrachten wir in jedem Fall, mit wie vielen $2$-Centmünzen man jeweils noch unterhalb von $10$ Cent bleibt, der verbleibende Rest wird mit $1$-Centmünzen aufgefüllt. Hierfür gibt es der Reihe nach

$6,3,1\text{ Möglichkeiten}.$

Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt

$1\cdot 6+1\cdot 3+2\cdot 1=11$

Möglichkeiten.

Aufgabe (3 Punkte)

Für ein doppelverpacktes Geschenk soll eine würfelförmige Schachtel in eine etwas größere würfelförmige Schachtel hineingelegt werden. Bestimme auf unterschiedliche Arten, wie viele Möglichkeiten es dafür gibt.

Lösung

Wir denken uns den größeren Würfel fest.

Es gibt $6$ Möglichkeiten, auf dem kleineren Würfel eine Seite auszusuchen, die der Boden sein soll. Wenn dies festgelegt ist, so gibt es noch $4$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind $24$ Möglichkeiten.

Es gibt $8$ Möglichkeiten, auf dem kleineren Würfel eine Ecke auszusuchen, die mit einer fixierten Ecke der größeren Würfelschachtel deckungsgleich werden soll. Wenn dies festgelegt ist, so gibt es noch $3$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind $24$ Möglichkeiten

Es gibt $12$ Möglichkeiten, auf dem kleineren Würfel eine Kante auszusuchen, die mit einer fixierten Kante der größeren Würfelschachtel deckungsgleich werden soll. Wenn dies festgelegt ist, so gibt es noch $2$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind $24$ Möglichkeiten

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

Eine $n$-Schokolade ist ein rechteckiges Raster, das durch $a-1$ Längsrillen und $b-1$ Querrillen in  $n=a\cdot b$  ($a,b\in {\mathbb{N}}_{+}$) mundgerechte kleinere Stücke eingeteilt ist. Ein Teilungsschritt an einer Schokolade ist das vollständige Durchtrennen einer Schokolade längs einer Längs- oder Querrille. Eine vollständige Aufteilung einer Schokolade ist eine Folge von Teilungsschritten (an der Ausgangsschokolade oder an einer zuvor erhaltenen Zwischenschokolade), deren Endprodukt aus den einzelnen Stücken besteht. Bei einer gegebenen vollständigen Aufteilung $A$ einer Schokolade kann man sich für jedes Stück $s$ fragen, wie oft es bei einem Teilungsschritt der Aufteilung beteiligt war. Diese Zahl nennen wir die Aufteilungstiefe von $s$. Die Summe aller Aufteilungstiefen zu allen Stücken nennen wir die Gesamtaufteilungstiefe der Aufteilung.

1. Es sei eine $4\times 4$-Schokolade gegeben. Zeige, dass es eine vollständige Aufteilung gibt, bei der jedes Stück die Aufspaltungstiefe $4$ besitzt.
2. Wir betrachten ein Eckstück einer $4\times 4$-Schokolade. Was ist seine minimale Aufteilungstiefe und was ist seine maximale Aufteilungstiefe?
3. Hängt für eine fixierte Schokolade die Gesamtaufteilungstiefe von der Aufteilung ab?

Lösung

1. Man halbiert zuerst in der Mitte, die beiden $2\times 4$-Schokoladen halbiert man so, dass jeweils $2\times 2$-Schokoladen entstehen, diese halbiert man wieder und die entstehenden $2\times 1$-Schokoladen halbiert man noch mal. Bei diesem Aufteilungsprozess ist jedes Stück an $4$ Teilungen beteiligt. Die Aufteilungstiefe ist also $4$ für jedes Stück.
2. Die minimale Aufteilungstiefe eines Eckstückes ist $2$, diese erreicht man, indem man von der Gesamtschokolade eine Einerreihe mit der Ecke abtrennt und daraus dann die Ecke als Einzelstück abtrennt. Aufteilungstiefe $1$ ist sicher nicht möglich. Die maximale Aufteilungstiefe ist $6$. Größer kann sie nicht sein, da es nur drei Quer- und drei Längsrillen gibt und die Anzahl der Rillen auf den Teilschokoladen bei jedem Teilungsschritt um zumindest $1$ kleiner wird. Unter der Aufteilung, bei der man stets eine die Ecke nicht enthaltende Einerrandreihe abtrennt, besitzt die Ecke die Aufteilungstiefe $6$.
3. Die Gesamtaufteilungstiefe hängt von der Aufteilung ab. Betrachten wir eine $4\times 1$-Schokolade. Wenn man in der Mitte halbiert und dann noch die beiden Teilschokoladen halbiert, so ist jedes Stück an zwei Teilungsvorgängen beteiligt, die Gesamtaufteilungstiefe ist also $8$. Wenn man hingegen jeweils ein Randstück abtrennt, so ist die Summe der Aufteilungstiefen gleich

   $1+2+3+3=9.$

Aufgabe (3 (2+1) Punkte)

Es seien $a,b$ positive natürliche Zahlen. Die Summe der Stammbrüche ist dann

$\frac{1}{a}+\frac{1}{b}=\frac{b+a}{ab}.$

a) Zeige, dass bei $a,b$ teilerfremd diese Darstellung gekürzt ist.

b) Zeige, dass im Allgemeinen diese Darstellung nicht gekürzt sein muss.

Lösung

a) Es seien $a$ und $b$ teilerfremd und es sei $p$ eine Primzahl. Wenn $p$ den Nenner $ab$ teilt, so teilt es nach dem Lemma von Euklid einen der Faktoren, sagen wir $a$. Dann teilt es wegen der Teilerfremdheit nicht auch $b$. Somit teilt es auch nicht $a+b$ und Zähler und Nenner sind teilerfremd.

b) Sei

$a=b=2.$

Dann ist

$\frac{1}{2}+\frac{1}{2}=\frac{2+2}{2\cdot 2}=\frac{4}{4}$

und dies ist keine teilerfremde Darstellung.

Aufgabe (1 Punkt)

Es sei $G$ eine Gruppe. Zeige, dass

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

für alle  $x\in G$  ist.

Lösung

Es ist

$x\circ x^{-1}=1.$

Damit ist $x$ das Inverse zu $x^{-1}$. Damit ist

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

Aufgabe (6 Punkte)

Zeige, dass es zu ganzen Zahlen $d,n$ mit  $d>0$  eindeutig bestimmte ganze Zahlen $q,r$ mit  $0\le r<d$  und mit

$n=dq+r$

gibt.

Lösung

Zur Existenz. Bei  $n=0$  ist  $q=r=0$  eine Lösung. Es sei $n$ positiv. Da $d$ positiv ist, gibt es ein Vielfaches  $ad\ge n$.  Daher gibt es auch eine Zahl $q$ mit $qd\le n$ und $(q+1)d>n$. Es sei  $r:=n-qd$.  Dann ist

$qd\le qd+r<qd+d$

und daher ist  $0\le r<d$  wie gewünscht. Bei $n$ negativ kann man  $-n=\tilde{q}d+\tilde{r}$  schreiben nach dem Resultat für positive Zahlen. Daraus ergibt sich

$n=(-\tilde{q})d-\tilde{r}=\{\begin{array}{c}(-\tilde{q})d+0\text{ bei }\tilde{r}=0\\ (-\tilde{q}-1)d+d-\tilde{r}\text{ sonst}.\end{array}$

Im zweiten Fall erfüllen $q=-\tilde{q}-1$ und $r=d-\tilde{r}$ die Bedingungen.
Zur Eindeutigkeit. Es sei

$qd+r=n=\tilde{q}d+\tilde{r},$

wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung  $\tilde{r}\ge r$.  Dann gilt  $(q-\tilde{q})d=\tilde{r}-r$.  Diese Differenz ist nichtnegativ und kleiner als $d$, links steht aber ein Vielfaches von $d$, sodass die Differenz $0$ sein muss und die beiden Darstellungen übereinstimmen.

Aufgabe weiter

Es sei $M$ die Menge der Mäuse und $L$ die Menge der Löcher auf einem Feld. Es wird beobachtet, dass jede Maus gewisse Löcher benutzt, andere dagegen vermeidet. Zu einer Teilmenge an Löchern  $S\subseteq L$  definieren wir

$S^{\perp }=\{m\in M\mid m\text{ benutzt alle Löcher aus }S\},$

und zu einer Teilmenge an Mäusen  $T\subseteq M$  definieren wir

$T^{\perp }=\{\ell \in L\mid \ell \text{ wird von jeder Maus aus }T\text{ benutzt}\}.$

1. Beschreibe zu einem Loch  $\ell \in L$  die Menge $\{\ell {\}}^{\perp }$ mit einem Satz.
2. Beschreibe die Menge $L^{\perp }$ mit einem Satz.
3. Beschreibe die Menge $M^{\perp }$ mit einem Satz.
4. Zeige: Zu Teilmengen  $S_1\subseteq S_2$  (in $L$) ist

   ${\left(S_1\right)}^{\perp }\supseteq {\left(S_2\right)}^{\perp }.$

5. Zeige: Für eine beliebige Teilmenge  $S\subseteq L$  ist

   $S\subseteq {\left(S^{\perp }\right)}^{\perp }.$

6. Zeige: Für eine Vereinigung

   $S=S_1\cup S_2\subseteq L$

   ist

   ${(S_1\cup S_2)}^{\perp }={\left(S_1\right)}^{\perp }\cap {\left(S_2\right)}^{\perp }.$

7. Gilt für einen Durchschnitt

   $S=S_1\cap S_2\subseteq L.$

   die Beziehung

   ${(S_1\cap S_2)}^{\perp }={\left(S_1\right)}^{\perp }\cup {\left(S_2\right)}^{\perp }?$

8. Gilt für eine beliebige Teilmenge  $S\subseteq L$  die Beziehung

   $S^{\perp }={\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }?$

Lösung

1. Das ist die Menge aller Mäuse, die dieses Loch benutzen.
2. Das ist die Menge derjenigen Mäuse, die jedes Loch benutzen.
3. Das ist die Menge derjenigen Löcher, die von allen Mäusen benutzt werden.
4. Es sei  $m\in {\left(S_2\right)}^{\perp }$.  Dies bedeutet, dass $m$ alle Löcher aus $S_2$ benutzt. Dann benutzt $m$ erst recht alle Löcher aus der Teilmenge $S_1$, also gilt  $m\in {\left(S_1\right)}^{\perp }$. 
5. Es sei  $\ell \in S$.  Die Menge $S^{\perp }$ besteht aus allen Mäusen, die alle Löcher aus $S$ benutzen. Diese Mäusemenge benutzt insbesondere $\ell$, daher ist  $\ell \in {\left(S^{\perp }\right)}^{\perp }$. 
6. Wegen  $S_1\subseteq S_1\cup S_2$  gilt nach Teil (4)

   ${(S_1\cup S_2)}^{\perp }\subseteq S_1^{\perp }$

   und entsprechend für $S_2$. Dies ergibt die Inklusion  ${(S_1\cup S_2)}^{\perp }\subseteq S_1^{\perp }\cap S_1^{\perp }$.  Es sei nun  $m\in S_1^{\perp }\cap S_1^{\perp }$.  Dies bedeutet, dass $m$ alle Löcher aus $S_1$ und alle Löcher aus $S_2$ benutzt. Also benutzt $m$ alle Löcher aus $S_1\cup S_2$, also  $m\in {(S_1\cup S_2)}^{\perp }$. 

7. Dies muss nicht gelten. Es kann beispielsweise $L$ disjunkt zerlegt in $S_1$ und $S_2$ sein. Dann ist  $S_1\cap S_2=\mathrm{\varnothing }$  und  ${\mathrm{\varnothing }}^{\perp }=M$.  Es kann aber gleichzeitig sein, dass es sowohl in $S_1$ als auch in $S_2$ jeweils ein Loch gibt, das von keiner Mausbenutzt wird. Dann ist

   ${\left(S_1\right)}^{\perp }=\mathrm{\varnothing }={\left(S_2\right)}^{\perp }.$

8. Das gilt. Nach (4) ist  $S\subseteq {\left(S^{\perp }\right)}^{\perp }$,  woraus mit (5) die Inklusion

   ${\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }\subseteq S^{\perp }.$

   Die zu (4) analoge Eigenschaft gilt auch für Teilmengen  $T\subseteq M$.  Angewendet auf  $T=S^{\perp }$,  ergibt sich

   $S^{\perp }\subseteq {\left({\left(S^{\perp }\right)}^{\perp }\right)}^{\perp }.$

Aufgabe (2 (1+1) Punkte)

Anna-Lena, Marie-Simone, Hans-Peter und Fritz-Franz gehen zur Farbberatung. Es ergibt sich folgende Empfehlung. Anna-Lena stehen die Farben grün, gelb und pink, Marie-Simone steht gelb und feuerrot, Hans-Peter steht grün, grau und graublau, Fritz-Franz stehen alle bisher genannten Farben außer graublau, dafür zusätzlich noch violett. Es sei $P$ die Menge der vier Personen und $F$ die Menge der erwähnten Farben zuzüglich blau.

1. Erstelle eine Tabelle und ein Verbindungsdiagramm, welche die Relation aus Personen und Farben wiedergeben.
2. Bestimme die Fasern zu blau, zu grün und zu Marie-Simone.

Lösung

1. 	grün	gelb	pink	feuerrot	grau	graublau	violett	blau
   Anna-Lena	$\text{x}$	$\text{x}$	$\text{x}$	$-$	$-$	$-$	$-$	$-$
   Marie-Simone	$-$	$\text{x}$	$-$	$\text{x}$	$-$	$-$	$-$	$-$
   Hans-Peter	$\text{x}$	$-$	$-$	$-$	$\text{x}$	$\text{x}$	$-$	$-$
   Fritz-Franz	$\text{x}$	$\text{x}$	$\text{x}$	$\text{x}$	$\text{x}$	$-$	$\text{x}$	$-$

2. Die Faser zu blau ist leer, die Faser zu grün ist $\{\text{Anna-Lena},\text{Hans-Peter},\text{Fritz-Franz}\}$ und die Faser zu Marie-Simone ist $\{\text{gelb},\text{feuerrot}\}$.

Aufgabe (4 Punkte)

Es sei $L$ eine vierelementige und $M$ eine dreielementige Menge. Bestimme die möglichen Faseranzahltupel und jeweils die Anzahl der Abbildungen von $L$ nach $M$, die dieses Faseranzahltupel besitzen.

Lösung

Die möglichen Faseranzahltupel sind $(0,0,4),(0,1,3),(0,2,2),(1,1,2)$.

Zur Bestimmung der Anzahlen verwenden wir die Formel aus Aufgabe 15.13 (Diskrete Mathematik (Osnabrück 2026)), wonach die Anzahl der Abbildungen mit vorgegebenem Fasertupel gleich

$\frac{k!}{m_0!\cdots m_n!}(\genfrac{}{}{0ex}{}{n}{r_1,\dots ,r_k})$

ist, wobei $m_j$ die Anzahl angibt, wie oft der Wert $j$ im Faseranzahltupel vorkommt.

$(0,0,4)$. Dies wird durch eine konstante Abbildung realisiert, davon gibt es $3$.

$(0,1,3)$.

Es ist

$\frac{3!}{1}\cdot \frac{4!}{3!}=6\cdot 4=24.$

$(0,2,2)$.

Es ist

$\frac{3!}{2!}\cdot \frac{4!}{2!2!}=3\cdot 6=18.$

$(1,1,2)$.

Es ist

$\frac{3!}{2!}\cdot \frac{4!}{2!}=3\cdot 12=36.$

Ferner ist  $3+24+18+36=81=3^4$,  was mit der Anzahl der Abbildungen überhaupt übereinstimmt.

Aufgabe (8 (1+1+2+2+2) Punkte)

Wir betrachten die reelle Matrixrekursion

$\left(\begin{array}{c}{u}_{n+1}\\ v_{n+1}\end{array}\right)=\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)\left(\begin{array}{c}{u}_n\\ v_n\end{array}\right).$

1. Bestimme das charakteristische Polynom von $\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$.
2. Bestimme die Eigenwerte von $\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$.
3. Bestimme eine Basis aus Eigenvektoren zu $\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right)$.
4. Schreibe $\left(\begin{array}{c}1\\ 0\end{array}\right)$ als Linearkombination der Basis aus (3).
5. Man gebe eine explizite Formel für die durch die Matrixrekursion definierte Folge $\left(\begin{array}{c}{u}_n\\ v_n\end{array}\right)$ zum Startvektor $\left(\begin{array}{c}1\\ 0\end{array}\right)$.

Lösung

1. Das charakteristische Polynom ist

   $\begin{array}{cc}det(\left(\begin{array}{cc}X& 0\\ 0& X\end{array}\right)-\left(\begin{array}{cc}1& 2\\ 3& 4\end{array}\right))& =det\left(\begin{array}{cc}X-1& -2\\ -3& X-4\end{array}\right)\\ & =(X-1)(X-4)-6\\ & =X^2-5X-2.\end{array}$

2. Die Nullstellen des charakteristischen Polynoms sind

   $x_{12}=\frac{\pm \sqrt{25+8}+5}{2}=\frac{\pm \sqrt{33}+5}{2},$

   das sind zugleich die Eigenwerte.

3. Der Kern von

   $\left(\begin{array}{cc}\frac{\sqrt{33}+5}{2}-1& -2\\ -3& \frac{\sqrt{33}+5}{2}-4\end{array}\right)=\left(\begin{array}{cc}\frac{\sqrt{33}+3}{2}& -2\\ -3& \frac{\sqrt{33}-3}{2}\end{array}\right)$

   ist

   $ℝ\left(\begin{array}{c}4\\ \sqrt{33}+3\end{array}\right),$

   $\left(\begin{array}{c}4\\ \sqrt{33}+3\end{array}\right)$ ist ein Eigenvektor zum Eigenwert $\frac{\sqrt{33}+5}{2}$.

   Der Kern von

   $\left(\begin{array}{cc}\frac{-\sqrt{33}+5}{2}-1& -2\\ -3& \frac{-\sqrt{33}+5}{2}-4\end{array}\right)=\left(\begin{array}{cc}\frac{-\sqrt{33}+3}{2}& -2\\ -3& \frac{-\sqrt{33}-3}{2}\end{array}\right)$

   ist

   $ℝ\left(\begin{array}{c}4\\ -\sqrt{33}+3\end{array}\right),$

   $\left(\begin{array}{c}4\\ -\sqrt{33}+3\end{array}\right)$ ist ein Eigenvektor zum Eigenwert $\frac{-\sqrt{33}+5}{2}$.

4. Es ist

   $\left(\begin{array}{c}1\\ 0\end{array}\right)=\frac{\sqrt{33}-3}{8\sqrt{33}}\left(\begin{array}{c}4\\ \sqrt{33}+3\end{array}\right)+\frac{\sqrt{33}+3}{8\sqrt{33}}\left(\begin{array}{c}4\\ -\sqrt{33}+3\end{array}\right).$

5. Gemäß Satz 16.6 (Diskrete Mathematik (Osnabrück 2026)) ist

   $\left(\begin{array}{c}{u}_n\\ v_n\end{array}\right)={\left(\frac{\sqrt{33}+5}{2}\right)}^n\cdot \frac{\sqrt{33}-3}{8\sqrt{33}}\cdot \left(\begin{array}{c}4\\ \sqrt{33}+3\end{array}\right)+{\left(\frac{-\sqrt{33}+5}{2}\right)}^n\cdot \frac{\sqrt{33}+3}{8\sqrt{33}}\cdot \left(\begin{array}{c}4\\ -\sqrt{33}+3\end{array}\right).$

Aufgabe (5 Punkte)

Beweise den Satz über den Zusammenhang von Graphen mit Blättern.

Lösung

Es sei $G$ zusammenhängend und  $u,v\in G\setminus \{b\}$.  Dann gibt es in $G$ einen verbindenden Weg von $u$ nach $v$. Wenn in diesem Weg $b$ vorkommt, so jedenfalls nicht als Anfangs- oder als Endpunkt, da dies explizit ausgeschlossen ist. Wenn $b$ in der Mitte vorkommt, so in der Form $w,b,w$, wobei $\{b,w\}$ die einzige Kante an $b$ bezeichne. Doch in diesem Fall kann man diesen Wegabschnitt herausnehmen und erhält einen kürzeren Weg von $u$ nach $v$. Deshalb gibt es auch einen verbindenden Weg, in dem $b$ gar nicht vorkommt.

Es sei nun $G\setminus \{b\}$ zusammenhängend und seien  $u,v\in G$.  Wenn  $u,v\ne b$  ist, so kann man direkt einen verbindenden Weg aus $G\setminus \{b\}$ nehmen. Wenn  $u=b$  ist, so ist $b$ mit einem weiteren Knotenpunkt $w$ verbunden, und einen Weg in $G\setminus \{b\}$ von $w$ nach $v$ kann man durch die Kante $\{b,w\}$ zu einem Weg in $G$ von $b$ nach $v$ verlängern.

Aufgabe (4 Punkte)

Beweise den Rekursionssatz für aufspannende Bäume.

Lösung

Es sei  $e=\{u,v\}$.  Ein Spannbaum in $G$ enthält entweder diese Kante oder nicht. Wir zeigen, dass es im ersten Fall eine Bijektion zu den Spannbäumen der Kontraktion $G/(e)$ und im zweiten Fall eine Bijektion zu den Spannbäumen von $G\setminus \{e\}$ gibt. Dies ist im zweiten Fall unmittelbar klar. Betrachten wir also die Spannbäume in $G$, in denen $e$ vorkommt. Wenn man diese Kante herausnimmt, so erhält man einen Spannbaum von $G/(e)$, da ja die Endpunkte von $e$ miteinander identifiziert werden und bei dieser Identifizierung wieder ein Baum entsteht. Es sei umgekehrt ein Spannbaum von $G/(e)$ gegeben. Dieser durchläuft jeden Punkt von $G/(e)$, also auch den Kontraktionspunkt  $[u]=[v]$.  Indem man die Kante $e$ an dieser Stelle einbaut, erhält man einen Spannbaum von $G$.

Aufgabe (1 Punkt)

Bestimme die Adjazenzmatrix zum vollständigen Graphen $K_n$.

Lösung

Die Adjazenzmatrix ist

$\left(\begin{array}{ccccc}0& 1& \dots & 1& 1\\ 1& 0& 1& \dots & 1\\ ⋮& \ddots & \ddots & \ddots & ⋮\\ 1& \dots & 1& 0& 1\\ 1& 1& \dots & 1& 0\end{array}\right).$

Aufgabe (3 Punkte)

Bestimme die Knotenüberdeckungszahl zum Spielzuggraphen des Königs auf einem $3\times 3$-Schachbrett.

Lösung

Die Knotenüberdeckungszahl ist $5$. Eine maximale Knotenüberdeckung erhält man durch den Mittelpunkt zusammen mit den vier Eckpunkten (oder den vier Seitenmittelpunkten). Wenn das Zentrum nicht zu einer Knotenüberdeckung gehört, so müssen alle acht Kanten, die vom Zentrum ausgehen, abgedeckt werden, und das wären schon acht Punkte. Eine optimale Knotenüberdeckung muss also das Zentrum beinhalten. Die verbleibenden acht Randkanten bilden einen Rundgang und man braucht vier (abwechselnde) Punkte für die Abdeckung. Die eingangs erwähnten Überdeckungen sind also optimal.

Aufgabe (2 Punkte)

Es sollen drei Häuser jeweils mit Leitungen an Wasser, Gas und Elektrizität angeschlossen werden. Beschreibe eine Möglichkeit, bei der es nur eine Überschneidung gibt.

Lösung erstellen