Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Fakultät einer natürlichen Zahl ${\displaystyle {}n}$.
2. Eine linksvollständige Relation ${\displaystyle {}R\subseteq M\times N}$.
3. Eine obere Schranke zu einer Teilmenge ${\displaystyle {}J\subseteq I}$ in einer geordneten Menge ${\displaystyle {}(I,\preccurlyeq )}$.
4. Ein starrer Graph.
5. Die Lapace-Matrix zu einem Multigraphen ${\displaystyle {}G}$.
6. Die chromatische Zahl eines Graphen.

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl in der Potenzmenge zu einer endlichen Menge.
2. Der Satz über die Beschreibung des Durchschnitts von Untergruppen von ${\displaystyle {}\mathbb {Z} }$.
3. Der Fünf-Farben-Satz.

Beweise den Satz über die Wohldefiniertheit der Anzahl einer endlichen Menge.

Seien die bijektiven Abbildungen

${\displaystyle \varphi \colon {\{1,\ldots ,n\}}\longrightarrow M}$

und

${\displaystyle \psi \colon \{1,\ldots ,k\}\longrightarrow M}$

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Fakt *****  (3) wieder bijektiv ist, ist auch

${\displaystyle \psi ^{-1}\circ \varphi \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}}$

bijektiv. Wir müssen also nur die endlichen Standardmengen ${\displaystyle {}{\{1,\ldots ,n\}}}$ untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

${\displaystyle \theta \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}}$

vorliegt, dass dann

${\displaystyle {}n=k\,}$

ist. Dies zeigen wir durch Induktion nach ${\displaystyle {}n}$. Wenn ${\displaystyle {}n=0}$ ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch ${\displaystyle {}k=0}$. Seien nun ${\displaystyle {}n,k}$ nicht ${\displaystyle {}0}$, so dass sie also jeweils einen Vorgänger haben. Es sei ${\displaystyle {}m}$ der Vorgänger von ${\displaystyle {}n}$ und ${\displaystyle {}\ell }$ der Vorgänger von ${\displaystyle {}k}$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

${\displaystyle {}z=\theta (n)\in \{1,\ldots ,k\}\,.}$

Dann gibt es nach der Herausnahme von ${\displaystyle {}n}$ bzw. ${\displaystyle {}z}$ eine bijektive Abbildung

${\displaystyle \{1,\ldots ,m\}={\{1,\ldots ,n\}}\setminus \{n\}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}.}$

Nach Fakt ***** gibt es eine bijektive Abbildung zwischen ${\displaystyle {}\{1,\ldots ,\ell \}}$ und ${\displaystyle {}\{1,\ldots ,k\}\setminus \{z\}}$. Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen ${\displaystyle {}\{1,\ldots ,m\}}$ und ${\displaystyle {}\{1,\ldots ,\ell \}}$. Nach Induktionsvoraussetzung ist ${\displaystyle {}m=\ell }$, also auch

${\displaystyle {}n=m'=\ell '=k\,.}$

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

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

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

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

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

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

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

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

${\displaystyle {}1\cdot 6+1\cdot 3+2\cdot 1=11\,}$

Möglichkeiten.

Im Sportunterricht wird ein Zirkeltraining mit den Stationen

Trampolin, Kletterwand, Schwebebalken, Basketballkorb, Laufband, Medizinball

durchgeführt. Bei einem Durchlauf soll die Kletterwand und der Schwebebalken unmittelbar hintereinander absolviert werden (die Reihenfolge ist aber egal), die beiden Ballstationen (Basketballkorb und Medizinball) sollen aber nicht unmittelbar hintereinander absolviert werden.

Wie viele Möglichkeiten (Reihenfolgen) gibt es für einen vollständigen Durchlauf, wenn diese beiden Bedingungen erfüllt sein sollen?

Wir betrachten zunächst die unmittelbar hintereinander zu absolvierenden Stationen Kletterwand und Schwebebalken als eine gemeinsame Station „Holz“. Damit gibt es ${\displaystyle {}5}$ Stationen. Es gibt ${\displaystyle {}{\binom {5}{2}}=10}$ Möglichkeiten, aus den ${\displaystyle {}5}$ Positionen ${\displaystyle {}2}$ Positionen auszusuchen, an denen der Basketballkorb bzw. der Medizinball absolviert wird. Darunter gibt es ${\displaystyle {}4}$ Möglichkeiten, bei denen beiden Ballstationen direkt hintereinander liegen. Somit gibt es ${\displaystyle {}10-4=6}$ erlaubte Auswahlen für die Positionen der beiden Ballstationen. Wenn diese festgelegt sind, so gibt es jeweils ${\displaystyle {}2}$ Möglichkeiten, welche der beiden Ballstationen an welcher Position durchgeführt wird, es gibt ${\displaystyle {}3!=6}$ Möglichkeiten, in welcher Reihenfolge die drei anderen Stationen (also Trampolin, Laufband und Holz) abgearbeitet werden, und dann gibt es noch jeweils ${\displaystyle {}2}$ Möglichkeiten für die Reihenfolge innerhalb der Holzstation. Insgesamt gibt es also

${\displaystyle {}6\cdot 6\cdot 2\cdot 2=144\,}$

erlaubte Reihenfolgen.

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring ${\displaystyle {}R}$ durch Induktion über ${\displaystyle {}k}$, wobei der Fall ${\displaystyle {}k=2}$ verwendet werden darf (dabei sind ${\displaystyle {}n_{1},\ldots ,n_{k}}$ natürliche Zahlen und ${\displaystyle {}a_{j,i}\in R}$).

${\displaystyle {}{\begin{aligned}{\left(\sum _{i_{1}=1}^{n_{1}}a_{1,i_{1}}\right)}\cdot {\left(\sum _{i_{2}=1}^{n_{2}}a_{2,i_{2}}\right)}\cdots {\left(\sum _{i_{k}=1}^{n_{k}}a_{k,i_{k}}\right)}&=\sum _{(i_{1},i_{2},\ldots ,i_{k})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\\\end{aligned}}}$

Sei die Aussage für ein bestimmtes ${\displaystyle {}k}$ bewiesen. Für ${\displaystyle {}k+1}$ Faktoren ist dann unter Verwendung der Induktionsvoraussetzung und unter Verwendung des Falles von zwei Faktoren

${\displaystyle {}{\begin{aligned}&{\left(\sum _{i_{1}=1}^{n_{1}}a_{1,i_{1}}\right)}\cdot {\left(\sum _{i_{2}=1}^{n_{2}}a_{2,i_{2}}\right)}\cdots {\left(\sum _{i_{k+1}=1}^{n_{k+1}}a_{k+1,i_{k+1}}\right)}\\&={\left(\sum _{(i_{1},i_{2},\ldots ,i_{k})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\right)}{\left(\sum _{i_{k+1}=1}^{n_{k+1}}a_{k+1,i_{k+1}}\right)}\\&={\left(\sum _{(i_{1},i_{2},\ldots ,i_{k},i_{k+1})\in \{1,\ldots ,n_{1}\}\times \{1,\ldots ,n_{2}\}\times \cdots \times \{1,\ldots ,n_{k}\}\times \{1,\ldots ,n_{k+1}\}}a_{1,i_{1}}\cdot a_{2,i_{2}}\cdots a_{k,i_{k}}\cdot a_{k+1,i_{k+1}}\right)}.\end{aligned}}}$

Die Karte zeigt Österreich mit seinen Bundesländern und den zugehörigen Hauptstädten (die Hauptstadt des Bundeslandes Wien ist Wien, Tirol ist ein Bundesland). Es sei ${\displaystyle {}M}$ die Menge der Bundesländer und sei ${\displaystyle {}R}$ die Relation auf ${\displaystyle {}M}$, die die Angrenzungsbeziehung (Nachbarschaftsbeziehung) beschreibt. Dabei legen wir fest, dass ein Land auch zu sich selbst benachbart ist.

1. Welche Eigenschaften einer Äquivalenzrelation erfüllt diese Relation?
2. Bestimme die Faser zu Kärnten.
3. Gibt es eine Kette ${\displaystyle {}x_{1},x_{2},\ldots ,x_{n}}$ in ${\displaystyle {}M}$ mit ${\displaystyle {}x_{i}Rx_{i+1}}$ für alle ${\displaystyle {}i}$, bei der jedes Bundesland genau einmal vorkommt?

1. Die Relation ist offenbar symmetrisch und aufgrund der Festlegung auch reflexiv. Sie ist nicht transitiv, da beispielsweise Kärnten und Steiermark und Steiermark und Niederösterreich benachbart sind, aber nicht Kärnten und Niederösterreich.
2. Die Faser zu Kärnten besteht aus Kärnten, Steiermark, Salzburg, Tirol.
3. Das ist möglich: Wien, Niederösterreich, Burgenland, Steiermark, Oberösterreich, Salzburg, Kärnten, Tirol, Vorarlberg.

Beweise das Lemma von Euklid für ganze Zahlen.

Wir setzen voraus, dass ${\displaystyle {}a}$ kein Vielfaches von ${\displaystyle {}p}$ ist (andernfalls sind wir fertig). Dann müssen wir zeigen, dass ${\displaystyle {}b}$ ein Vielfaches von ${\displaystyle {}p}$ ist. Unter der gegebenen Voraussetzung sind ${\displaystyle {}a}$ und ${\displaystyle {}p}$ teilerfremd. Nach dem Lemma von Bezout gibt es ganze Zahlen ${\displaystyle {}r,s}$ mit

${\displaystyle {}ra+sp=1\,}$

Da ${\displaystyle {}ab}$ ein Vielfaches von ${\displaystyle {}p}$ ist, gibt es ein ${\displaystyle {}t}$ mit

${\displaystyle {}ab=tp\,.}$

Daher ist

${\displaystyle {}b=b\cdot 1=b(ra+sp)=abr+bsp=tpr+bsp=p{\left(tr+bs\right)}\,.}$

Also ist ${\displaystyle {}b}$ ein Vielfaches von ${\displaystyle {}p}$.

Bestimme das inverse Element zu ${\displaystyle {}{\overline {55}}}$ in ${\displaystyle {}\mathbb {Z} /(93)}$.

Der euklidische Algorithmus liefert

${\displaystyle {}93=1\cdot 55+38\,,}$

${\displaystyle {}55=1\cdot 38+17\,,}$

${\displaystyle {}38=2\cdot 17+4\,,}$

${\displaystyle {}17=4\cdot 4+1\,.}$

Somit ist

${\displaystyle {}{\begin{aligned}1&=17-4\cdot 4\\&=17-4\cdot (38-2\cdot 17)\\&=9\cdot 17-4\cdot 38\\&=9\cdot {\left(55-38\right)}-4\cdot 38\\&=9\cdot 55-13\cdot 38\\&=9\cdot 55-13\cdot {\left(93-55\right)}\\&=22\cdot 55-13\cdot 93.\end{aligned}}}$

Daher ist

${\displaystyle 22}$

das inverse Element zu ${\displaystyle {}55}$ in ${\displaystyle {}\mathbb {Z} /(93)}$.

Es seien ${\displaystyle {}M}$ und ${\displaystyle {}N}$ endliche Mengen mit ${\displaystyle {}m}$ bzw. ${\displaystyle {}n}$ Elementen und sei

${\displaystyle f\colon M\longrightarrow N}$

eine surjektive Abbildung. Wie viele Abbildungen

${\displaystyle s\colon N\longrightarrow M}$

mit

${\displaystyle {}f\circ s=\operatorname {Id} _{N}\,}$

gibt es?

Die Elemente aus ${\displaystyle {}N}$ seien mit ${\displaystyle {}1,2,\ldots ,n}$ bezeichnet. Zu jedem ${\displaystyle {}i\in N}$ sei

${\displaystyle {}M_{i}={\left\{x\in M\mid f(x)=i\right\}}\,}$

und

${\displaystyle {}m_{i}={\#\left(M_{i}\right)}={\#\left({\left\{x\in M\mid f(x)=i\right\}}\right)}\,}$

die Anzahl der Elemente aus ${\displaystyle {}M}$, die auf ${\displaystyle {}i}$ abgebildet werden. Wegen der Surjektivität ist stets ${\displaystyle {}m_{i}\geq 1}$. Da

${\displaystyle {}f\circ s=\operatorname {Id} _{N}\,}$

gelten soll, muss ${\displaystyle {}s(i)\in M_{i}}$ für jedes ${\displaystyle {}i}$ gelten. Somit gibt es

${\displaystyle m_{1}\cdot m_{2}\cdots m_{n}}$

Möglichkeiten für solche Abbildungen.

Es sei ${\displaystyle {}\varphi \colon G\rightarrow H}$ ein Graphhomomorphismus.

1. Es sei ${\displaystyle {}\varphi }$ injektiv. Zeige, dass für den Grad die Abschätzung

   ${\displaystyle {}d(P)\leq d(\varphi (P))\,}$

   für jeden Punkt ${\displaystyle {}P\in G}$ gilt.

2. Wie sieht es aus, wenn ${\displaystyle {}\varphi }$ nicht injektiv ist?

1. Es seien ${\displaystyle {}v_{1},\ldots ,v_{n}}$ die an ${\displaystyle {}P}$ anliegenden Punkte, also ${\displaystyle {}d(P)=n}$. Diese werden auf verschiedene Punkte ${\displaystyle {}\varphi (v_{i})}$ abgebildet und es ist stets ${\displaystyle {}\varphi (P)\varphi (v_{i})}$ eine Kante von ${\displaystyle {}H}$. Also liegen an ${\displaystyle {}\varphi (P)}$ zumindest ${\displaystyle {}n}$ Kanten an.
2. Ohne die Voraussetzung injektiv ist die Aussage aus (1) nicht richtig. Betrachten wir den linearen Graphen ${\displaystyle {}1,2,3}$, also mit den zwei Kanten ${\displaystyle {}\{1,2\}}$ und ${\displaystyle {}\{2,3\}}$, und die Abbildung auf den linearen Graphen ${\displaystyle {}a,b}$, also mit der Kante ${\displaystyle {}\{a,b\}}$, der ${\displaystyle {}1}$ und ${\displaystyle {}3}$ auf ${\displaystyle {}a}$ und ${\displaystyle {}2}$ auf ${\displaystyle {}b}$ abbildet. Da Kanten auf Kanten gehen, liegt ein Graphhomomorphismus vor. Der Grad von ${\displaystyle {}2}$ ist aber gleich ${\displaystyle {}2}$, während der Grad von ${\displaystyle {}b}$ gleich ${\displaystyle {}1}$ ist.

Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem ${\displaystyle {}3\times 3}$-Brett wie abgebildet.

1. Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.
2. Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

1. Die zwei weißen horizontalen Felder (links bzw. rechts) und die beiden weißen vertikalen Felder (oben bzw. unten) bilden eine bipartite Zerlegung. Bei einem Läuferzug auf diesen weißen Feldern wird stets von einem horizontalen zu einem vertikalen Feld und umgekehrt hinübergewechselt.
2. Betrachten wir die Hauptdiagonale. Der schwarzfeldrige Läufer kann von links unten in die Mitte und dann nach rechts oben und von dort direkt wieder nach links unten ziehen. Dies ist ein Kreis der Länge ${\displaystyle {}3}$, was es nach Fakt ***** in einem bipartiten Graphen nicht gibt.

Begründe, dass der abgebildete Graph hamiltonsch ist.