Kurs:Diskrete Mathematik/13/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	2	4	2	4	3	4	6	3	2	3	2	2	4	10	4	4	65

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Der Graph zu einer Abbildung ${}F\colon L\rightarrow M$.
2. Ein maximales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Ein Verband (algebraische Definition).
4. Der Komplementärgraph zu einem Graphen ${}G=(V,E)$.
5. Ein Kreis in einem Graphen.
6. Ein Eulerscher Kantenzug in einem Graphen ${}G=(V,E)$.

Lösung

1. Man nennt

   $\Gamma _{F}={\left\{(x,F(x))\mid x\in L\right\}}\subseteq L\times M$

   den Graphen der Abbildung ${}F$.

2. Ein Element ${}x\in I$ heißt maximal, wenn es kein Element ${}y\in I$, ${}y\neq x$, mit ${}x\preccurlyeq y$ gibt.
3. Eine Menge ${}M$ mit zwei kommutativen und assoziativen Verknüpfungen ${}\sqcup$ und ${}\sqcap$ heißt algebraischer Verband, wenn die Absorptionsgesetze

   ${}x\sqcup (x\sqcap y)=x\,$

   und

   ${}x\sqcap (x\sqcup y)=x\,$

   gelten.

4. Man nennt ${}(V,{\mathfrak {P}}_{2}\,(V)\setminus E)$ den komplementären Graphen zu ${}G$.
5. Ein Kreis in einem Graphen ist ein Zyklus der Länge ${}\geq 3$ ohne Wiederholungen.
6. Ein Kantenzug ${}e_{1},\ldots ,e_{m}$ in ${}G$ heißt eulersch, wenn in ihm jede Kante aus ${}E$ genau einmal vorkommt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von fixpunktfreien Permutationen.
2. Der Satz über die Gradsumme in einem Graphen.
3. Der Satz von Berge.

Lösung

1. Die Anzahl der fixpunktfreien Permutationen auf einer Menge mit ${}n$ Elementen ist

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

2. In einem Graphen ${}(V,E)$ gilt

   ${}\sum _{v\in V}d(v)=2\cdot {\#\left(E\right)}\,.$

3. Eine Paarung ${}P$ in einem Graphen ${}G$ ist genau dann optimal, wenn es keinen alternierenden Weg gibt, dessen Endpunkte verschieden und unabgedeckt sind.

Aufgabe (2 Punkte)

Am Weihnachtsbaum gibt es ${}10$ Kerzen. Berechne die Anzahl der Reihenfolgen, wie die Kerzen angezündet werden können.

Lösung

Die Anzahl der möglichen Reihenfolgen ist ${}10!$. Dies ist

${}{\begin{aligned}10!&=10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1\\&=100\cdot 9\cdot 8\cdot 7\cdot 6\cdot 4\cdot 3\\&=100\cdot 72\cdot 72\cdot 7\\&=3628800.\end{aligned}}$

Aufgabe (4 Punkte)

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

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

ist.

Lösung

Wir beweisen die Aussage durch Induktion nach ${}n$. Die Aussage ist für ${}n=0$ klar, sei also angenommen, die Aussage sei für ein beliebiges ${}n$ (für alle ${}k$) schon bewiesen, und betrachten wir eine ${}(n+1)$-elementige Menge ${}M$. Diese Menge ist wegen ${}n\geq 0$ nicht leer. Wir fixieren ein Element ${}a\in M$ und betrachten die ${}n$-elementige Teilmenge ${}M\setminus \{a\}\subset M$. Jede Teilmenge von ${}M$ enthält entweder ${}a$ oder nicht. Daher lassen sich die ${}k$-elementigen Teilmengen von ${}M$ aufteilen in ${}k$-elementige Teilmengen von ${}M\setminus \{a\}$ (das sind diejenigen Teilmengen, die nicht ${}a$ enthalten), und die ${}(k-1)$-elementigen Teilmengen von ${}M\setminus \{a\}$ (eine solche ${}(k-1)$-elementige Teilmenge ${}T$ definiert die ${}k$-elementige Teilmenge ${}T\cup \{a\}$ in ${}M$). Daher ist die Gesamtzahl der ${}k$-elementigen Teilmengen von ${}M$ nach Lemma 2.16 (Diskrete Mathematik (Osnabrück 2020)) gleich

${}{\binom {n}{k}}+{\binom {n}{k-1}}={\binom {n+1}{k}}\,.$

Aufgabe (2 Punkte)

Es seien ${}(M,*)$ und ${}(N,\circ )$ Mengen mit Verknüpfungen und es sei

$\varphi \colon M\longrightarrow N$

eine mit den Verknüpfungen verträgliche surjektive Abbildung, es gelte also

${}\varphi (x*y)=\varphi (x)\circ \varphi (y)\,.$

Die Verknüpfung auf ${}M$ sei assoziativ. Zeige, dass auch die Verknüpfung auf ${}N$ assoziativ ist.

Lösung

Es seien ${}r,s,t$ Elemente in ${}N$. Wegen der Surjektivität gibt es Elemente ${}x,y,z\in M$ mit ${}\varphi (x)=r$, ${}\varphi (y)=s$, ${}\varphi (z)=t$. Somit ist unter Verwendung der Assoziativität von ${}*$ und der Verträglichkeit

${}{\begin{aligned}r\circ (s\circ t)&=\varphi (x)\circ (\varphi (y)\circ \varphi (z))\\&=\varphi (x)\circ \varphi (y*z)\\&=\varphi (x*(y*z))\\&=\varphi ((x*y)*z)\\&=\varphi (x*y)\circ \varphi (z)\\&=(\varphi (x)\circ \varphi (y))\circ \varphi (z)\\&=(r\circ s)\circ t.\end{aligned}}$

Aufgabe (4 (1+1+1+1) Punkte)

Es sei ${}(M,\preccurlyeq )$ eine nichtleere geordnete Menge. Wir betrachten die Relation ${}\prec$ auf ${}M$, die durch ${}x\prec y$, falls ${}x\preccurlyeq y$ und ${}x\neq y$ gilt, definiert ist.

1. Ist ${}\prec$ transitiv?
2. Ist ${}\prec$ reflexiv?
3. Charakterisiere, wann ${}\prec$ symmetrisch ist.
4. Ist ${}\prec$ antisymmetrisch?

Lösung

1. Sei ${}x\prec y$ und ${}y\prec z$. Das bedeutet ${}x\preccurlyeq y$ und ${}y\preccurlyeq z$ und somit ist wegen der Transitivität von ${}\preccurlyeq$ auch ${}x\preccurlyeq z$. Wäre ${}x=z$, so wäre wegen der Antisymmetrie von ${}\preccurlyeq$ auch ${}x=y$, was den Voraussetzungen widerspricht.
2. Die Relation ${}\prec$ ist nicht reflexiv, da ${}x\prec y$ die Verschiedenheit von ${}x$ und ${}y$ beinhaltet.
3. Die Relation ${}\prec$ ist nicht symmetrisch, außer wenn ${}\preccurlyeq$ die Identität ist. In diesem Fall ist nämlich ${}\prec$ die leere Relation, und diese ist symmetrisch. Wenn es hingegen ein Paar ${}x\preccurlyeq y$ mit ${}x\neq y$ gibt, so ist ${}x\prec y$, aber nicht umgekehrt.
4. Die Relation ${}\prec$ ist antisymmetrisch. Sei ${}x\prec y$ und ${}y\prec x$. Dann ist insbesondere${}x\preccurlyeq y$ und ${}y\preccurlyeq x$ und die Antisymmetrie der Ordnungsrelation impliziert ${}x=y$. Doch dies ist ein Widerspruch zur Voraussetzung. D.h. die Voraussetzung in der Eigenschaft Antisymmetrie kann gar nicht erfüllt sein und daher ist die Antisymmetrie erfüllt.

Aufgabe (3 Punkte)

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheit ${}\neg (x\sqcap y)=\neg x\sqcup \neg y$ für alle ${}x,y\in V$ gilt.

Lösung

Wir zeigen, dass ${}x\sqcap y$ komplementär zu ${}\neg x\sqcup \neg y$ ist. Wegen der Eindeutigkeit des Komplements in einem booleschen Verband ist dies die Behauptung. Unter Verwendung der Distributivgesetze ist einerseits

${}{\begin{aligned}(x\sqcap y)\sqcup (\neg x\sqcup \neg y)&=(x\sqcup (\neg x\sqcup \neg y))\sqcap (y\sqcup (\neg x\sqcup \neg y))\\&=(x\sqcup \neg x\sqcup \neg y)\sqcap (y\sqcup \neg x\sqcup \neg y)\\&=(1\sqcup \neg y)\sqcap (1\sqcup \neg x)\\&=1\sqcap 1\\&=1\end{aligned}}$

und andererseits

${}{\begin{aligned}(x\sqcap y)\sqcap (\neg x\sqcup \neg y)&=((x\sqcap y)\sqcap \neg x))\sqcup ((x\sqcap y)\sqcap \neg y))\\&=(0\sqcap y)\sqcup (0\sqcap x)\\&=0\sqcup 0\\&=0.\end{aligned}}$

Aufgabe (4 Punkte)

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen. Zeige, dass

${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,$

ist, wobei ${}u$ das kleinste gemeinsame Vielfache der ${}a_{1},\ldots ,a_{k}$ ist.

Lösung

Nach Aufgabe 6.14 (Diskrete Mathematik (Osnabrück 2020)) ist der Durchschnitt der Untergruppen ${}\mathbb {Z} a_{i}$ wieder eine Untergruppe von ${}\mathbb {Z}$. Nach Satz 8.4 (Diskrete Mathematik (Osnabrück 2020)) gibt es ein eindeutig bestimmtes ${}c\geq 0$ mit

${}\mathbb {Z} a_{1}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} c\,.$

Wegen ${}\mathbb {Z} c\subseteq \mathbb {Z} a_{i}$ für alle ${}i$ ist ${}c$ ein Vielfaches von jedem ${}a_{i}$, also ein gemeinsames Vielfaches der ${}a_{1},\ldots ,a_{k}$. Für jedes gemeinsame Vielfache ${}v$ dieser Elemente gilt

${}\mathbb {Z} v\subseteq \mathbb {Z} a_{1}\cap \ldots \cap \mathbb {Z} a_{k}\,.$

Die Zahl ${}c$ besitzt also die Eigenschaft, dass jedes gemeinsame Vielfache der Elemente ein Vielfaches von ${}c$ ist. Daher ist ${}c$ das kleinste gemeinsame Vielfache.

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

Es sei ${}K$ ein Körper und ${}V\neq 0$ ein endlichdimensionaler ${}K$- Vektorraum.

1. Wir betrachten auf ${}V$ die Relation ${}R$, die durch ${}uRv$ gegeben ist, falls es eine lineare Abbildung ${}\varphi \colon V\rightarrow V$ mit ${}\varphi (u)=v$ gibt. Welche Eigenschaften einer Äquivalenzrelation sind erfüllt, welche nicht?
2. Wir betrachten auf ${}V$ die Relation ${}S$, die durch ${}uSv$ gegeben ist, falls es eine bijektive lineare Abbildung ${}\varphi \colon V\rightarrow V$ mit ${}\varphi (u)=v$ gibt. Zeige, dass dies eine Äquivalenzrelation ist.
3. Bestimme die Äquivalenzklassen zur Äquivalenzrelation ${}S$ aus (2).

Lösung

1. Die Relation ist reflexiv, da man für ${}\varphi$ die Identität nehmen kann, und sie ist transitiv, da es bei ${}uRv$ und ${}vRw$ lineare Abbildungen ${}\varphi ,\psi$ mit

   ${}\varphi (u)=v\,$

   und

   ${}\psi (v)=w\,$

   gibt. Daher ist insgesamt

   ${}(\psi \circ \varphi )(u)=w\,$

   und somit ${}uRw$. Die Relation ist nicht symmetrisch, da aufgrund der Existenz der Nullabbildung stets ${}xR0$ gilt, aber umgekehrt ${}0Rx$ nur bei ${}x=0$ gilt.

2. Wenn man sich auf bijektive Abbildungen beschränkt, so liegt eine Äquivalenzrelation vor. Die Argumentation für die Reflexivität und die Transititvität ist wie in Teil (1), da ja die Verknüpfung von bijektiven Abbildungen wieder bijektiv ist. Wenn ${}uSv$ gilt, so bedeutet dies die Existenz einer bijektiven linearen Abbildung ${}\varphi$ mit

   ${}\varphi (u)=v\,.$

   Somit ist

   ${}u=\varphi ^{-1}(v)\,$

   und daher ${}vRu$.

3. Es gibt zwei Äquivalenzklassen. Der Nullpunkt ${}0$ ist nur zu sich selbst äquivalent, da unter jeder linearen Abbildung ${}0$ auf sich selbst abgebildet wird. Hingegen sind je zwei Vektoren ${}u,v$, die beide nicht ${}0$ sind, untereinander äquivalent. Man kann sie nämlich jeweils zu einer Basis ${}u_{1}=u,u_{2},\ldots ,u_{n}$ bzw. ${}v_{1}=v,v_{2},\ldots ,v_{n}$ von ${}V$ ergänzen. Aufgrund des Festlegungssatzes gibt es eine lineare Abbildung mit ${}\varphi (u_{i})=v_{i}$, also insbesondere mit ${}\varphi (u)=v$, und diese ist bijektiv, da sie eine Basis auf eine Basis abbildet.

Aufgabe (3 Punkte)

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

Lösung

Der euklidische Algorithmus liefert

${}101=2\cdot 35+31\,,$

${}35=1\cdot 31+4\,,$

${}31=7\cdot 4+3\,,$

${}4=1\cdot 3+1\,.$

Somit ist

${}{\begin{aligned}1&=4-1\cdot 3\\&=4-1\cdot (31-7\cdot 4)\\&=8\cdot 4-1\cdot 31\\&=8\cdot (35-31)-1\cdot 31\\&=8\cdot 35-9\cdot 31\\&=8\cdot 35-9\cdot (101-2\cdot 35)\\&=26\cdot 35-9\cdot 101.\end{aligned}}$

Daher ist ${}26$ das inverse Element zu ${}35$ in ${}\mathbb {Z} /(101)$.

Aufgabe (2 Punkte)

Es sei ${}M=\{1,2,3,4,5,6,7\}$ und ${}N=\{a,b,c,d\}$. Bestimme die Anzahl der surjektiven Abbildungen von ${}M$ nach ${}N$ mit der zusätzlichen Eigenschaft, dass jedes Element aus ${}N$ höchstens zweimal getroffen wird.

Lösung

Für die Anzahl der Fasern gibt es unter der beschriebenen Bedingung nur die Möglichkeit ${}(2,2,2,1)$ mit Permutationen. Deshalb ist die Anzahl gleich

${}4\cdot {\binom {7}{2,2,2,1}}=4\cdot {\frac {7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}{8}}=7\cdot 6\cdot 5\cdot 4\cdot 3=2520\,.$

Aufgabe (3 (0.5+1+0.5+1) Punkte)

Bestimme zum Netzgraphen ${}G$ der Metro Manila die folgenden graphentheoretischen Invarianten (dabei gelten Recto und Doroteo Jose als eine Station, EDSA und Taft Avenue gelten als eine Station, Araneta Center und Cubao gelten als eine Station. North Avenue und Roosevelt sind durch eine Kante verbunden).

1. Die Blätter von ${}G$.
2. Die Exzentrizität von Pureza.
3. Den Maximalgrad von ${}G$. In welchen Stationen wird er angenommen?
4. Die Taille von ${}G$.

Lösung

1. Die Blätter sind Santolan und Baclaran.
2. Der Abstand von Pureza nach Santolan ist ${}8$, der Abstand nach Baclaran ist ${}12$. Der obere Kreis hat die Länge ${}20$, der maximale Abstand dadrauf ist also ${}10$, der untere Kreis hat die Länge ${}25$, der maximale Abstand dadrauf ist also ${}12$. Die Exzentrizität ist also ${}12$ (und wird in Bacalaran, Magalianes und Ayala angenommen).
3. Der Maximalgrad ist ${}4$, er wird in Araneta Center/Cubao angenommen.
4. Wie oben berechnet besitzt der obere Kreis die Länge ${}20$ und der untere die Länge ${}25$, der umfahrende Kreis hat eine größere Länge. Die Taille ist also ${}20$.

Aufgabe (2 Punkte)

Skizziere einen zusammenhängenden Graphen, in dem es genau einen Knoten mit dem Grad ${}2$, genau einen Knoten mit dem Grad ${}3$, genau einen Knoten mit dem Grad ${}4$, ... und genau einen Knoten mit dem Grad ${}8$ gibt.

Lösung

Aufgabe (2 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Lösung

Der isolierte Punkt ${}A$ muss unter einem Graphautomorphismus auf sich selbst abgebildet werden. ${}B$ und ${}C$ können offenbar miteinander vertauscht werden. Deshalb gibt es neben der Identität diese Vertauschung und die Automorphismengruppe ist ${}\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 (10 Punkte)

Beweise den Paarungssatz (Heiratssatz).

Lösung

Wir führen Induktion über die Anzahl von ${}I$, bei ${}I=\{i\}$ ist nach Voraussetzung ${}M_{i}\neq \emptyset$ und man kann ein beliebiges Element aus ${}M_{i}$ als Wert an der Stelle ${}i$ festlegen.

Es sei nun ${}I$ ${}n$-elementig und sei die Aussage für jede kleinere Indexmenge (und jede Mengenfamilie, die die numerische Bedingung erfüllt) bewiesen. Wir betrachten zwei Fälle. Erster Fall. Für alle Teilmengen ${}J\subseteq I$, ${}J\neq \emptyset ,I$, gelte sogar die stärkere Bedingung

${}{\#\left(M_{J}\right)}\geq {\#\left(J\right)}+1\,.$

Wir wählen ein Element ${}i_{0}\in I$ und ${}m_{0}\in M_{i_{0}}$ und betrachten ${}I':=I\setminus \{i_{0}\}$, ${}M'=M\setminus \{m_{0}\}$, ${}M_{i}'=M_{i}\setminus \{m_{0}\}$. Da stets nur das Element ${}m_{0}$ herausgenommen wird, gilt die numerische Bedingung für diese neue Situation und wir können darauf die Induktionsvoraussetzung anwenden. Es gibt also eine injektive Abbildung

$g\colon I'\longrightarrow M'$

mit ${}g(i)\in M_{i}'$. Diese Abbildung können wir durch ${}i_{0}\mapsto m_{0}$ zu einer injektiven Abbildung von ${}I$ nach ${}M$ fortsetzen. Zweiter Fall. Es gibt nun eine echte Teilmenge ${}\emptyset \subset J\subset I$ mit

${}{\#\left(J\right)}={\#\left(M_{J}\right)}\,.$

Für ${}J$ gilt die numerische Bedingung nach wie vor. Wir betrachten

${}K:=I\setminus J\,$

und

${}N:=M\setminus M_{J}\,$

und setzen

${}N_{k}:=M_{k}\cap N\,$

für ${}k\in K$. Für jede Teilmenge ${}T\subseteq K$ ist

${}{\begin{aligned}\bigcup _{k\in T\cup J}M_{k}&={\left({\left(\bigcup _{k\in T}M_{k}\right)}\setminus {\left(\bigcup _{k\in J}M_{k}\right)}\right)}\cup {\left(\bigcup _{k\in J}M_{k}\right)}\\&={\left(\bigcup _{k\in T}N_{k}\right)}\uplus {\left(\bigcup _{k\in J}M_{k}\right)}\\&={\left(\bigcup _{k\in T}N_{k}\right)}\uplus M_{J}.\end{aligned}}$

Nach Voraussetzung hat diese Menge zumindest ${}{\#\left(T\right)}+{\#\left(J\right)}$ Elemente und ${}M_{J}$ hat genau ${}{\#\left(J\right)}$ Elemente. Deshalb besitzt ${}\bigcup _{k\in T}N_{k}$ zumindest ${}{\#\left(T\right)}$ Elemente. D.h. dass ${}K$ und die ${}N_{k}$, ${}k\in K$, ebenfalls die numerische Bedingung erfüllen. Wir können die Induktionsvoraussetzung auf ${}J$ einerseits und auf ${}K$ andererseits (mit den zugehörigen Zielmengen) anwenden und erhalten injektive Abbildungen

$g\colon J\longrightarrow M_{J}$

mit ${}g(j)\in M_{j}$ und

$h\colon K\longrightarrow N$

mit ${}h(k)\in N_{k}\subseteq M_{k}$. Da ${}M_{J}$ und ${}N$ disjunkt sind, setzen sich diese beiden Abbildungen zu einer injektiven Abbildung ${}f\colon I\rightarrow M$ mit ${}f(i)\in M_{i}$ zusammen.

Aufgabe (4 Punkte)

Bestimme das chromatische Polynom zum vollständigen bipartiten Graphen ${}K_{2,s}$.

Lösung

Es stehen ${}k$ Farben zur Verfügung, wobei die beiden Teilmengen der bipartiten Zerlegung ${}V=A\uplus B$ auf verschiedene Farben Bezug nehmen. Wenn die zweielementige Menge ${}A$ auf nur eine Farbe Bezug nimmt, so gibt es ${}(k-1)^{s}$ zulässige Färbungen von diesem Typ, da für die ${}s$-elementige Menge ${}B$ genau ${}k-1$ Farben zur Verfügung stehen ohne weitere Bedingung. Für die Farbe für ${}A$ haben wir ${}k$ Möglichkeiten, das ergibt insgesamt ${}k(k-1)^{s}$. Wenn die zweielementige Menge auf zwei Farben Bezug nimmt, so gibt es ${}(k-2)^{s}$ zulässige Färbungen von diesem Typ. Für die Farben für ${}A$ haben wir ${}{\binom {k}{2}}$ Möglichkeiten, was wir mit ${}2$ wegen der beiden möglichen Reihenfolgen multiplizieren müssen. Das ergibt insgesamt ${}k(k-1)(k-2)^{s}$.

Insgesamt ist also

${}P_{}\left(k\right)=k(k-1)^{s}+k(k-1)(k-2)^{s}\,.$

Aufgabe (4 Punkte)

Für welche der Schachfiguren Turm, Läufer, Dame, König ist der Spielzuggraph zu einem ${}8\times 8$-Feld planar?

Lösung

Zum Turm betrachten wir die ${}5$ Felder einer fixierten Zeile, die alle untereinander durch einen Turmzug erreichbar sind. Das ist also ein vollständiger Untergraph mit ${}5$ Knotenpunkten. Nach Beispiel 25.7 (Diskrete Mathematik (Osnabrück 2020)) ist dieser nicht planar und daher ist auch der Spielzuggraph zum Turm nicht planar. Für den Läufer betrachten wir ${}5$ Felder auf der Hauptidagonalen (oder Hauptnebendiagonalen). Dies ist ebenfalls ein vollständiger Graph mit ${}5$ Knotenpunkten und somit nicht planar. Der Spielzuggraph zur Dame ist aus dem gleichen Grund nicht planar.

Der Spielzuggraph zum König ist ebenfalls nicht planar. Er besitzt ${}56$ horizontale Kanten, ${}56$ vertikale Kanten und ${}2\cdot 49$ diagonale Kanten. Deshalb gibt es insgesamt ${}210$ Kanten. Bei einem planaren Graphen mit ${}64$ Knoten darf es aber nach Korollar 25.6 (Diskrete Mathematik (Osnabrück 2020))  (1) höchstens

${}3\cdot 64-6=186\,$

Kanten geben.