Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Relation/Linkseindeutig/Definition/Begriff
2. Verband/Boolesch/Definition/Begriff
3. Eine Äquivalenzrelation ${\displaystyle {}\sim }$ auf einer Menge ${\displaystyle {}M}$.
4. Ungerichteter Graph/Automorphismengruppe/Homogen/Definition/Begriff
5. Ungerichteter Graph/Aufspannender Wald/Definition/Begriff
6. Ungerichter Graph/Knotenteilmenge/Paarung/Definition/Begriff

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

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 ${\displaystyle {}P}$ die Menge der vier Personen und ${\displaystyle {}F}$ die Menge der erwähnten Farben zuzüglich blau.

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

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

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

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.

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

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

Es gibt ${\displaystyle {}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 ${\displaystyle {}3}$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind ${\displaystyle {}24}$ Möglichkeiten

Es gibt ${\displaystyle {}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 ${\displaystyle {}2}$ Drehmöglichkeiten, wie der Würfel zu platzieren ist. Dies sind ${\displaystyle {}24}$ Möglichkeiten

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

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

1. Zeige, dass bei ${\displaystyle {}a,b}$ teilerfremd diese Darstellung gekürzt ist.
2. Zeige, dass im Allgemeinen diese Darstellung nicht gekürzt sein muss.

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

   ${\displaystyle {}a=b=2\,.}$

   Dann ist

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

   und dies ist keine teilerfremde Darstellung.

Sei ${\displaystyle {}G}$ eine Gruppe. Zeige, dass

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

für alle ${\displaystyle {}x\in G}$ ist.

Es ist

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

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

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

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

${\displaystyle {}n=dq+r\,}$

gibt.

Zur Existenz. Bei ${\displaystyle {}n=0}$ ist ${\displaystyle {}q=r=0}$ eine Lösung. Sei ${\displaystyle {}n}$ positiv. Da ${\displaystyle {}d}$ positiv ist, gibt es ein Vielfaches ${\displaystyle {}ad\geq n}$. Daher gibt es auch eine Zahl ${\displaystyle {}q}$ mit ${\displaystyle qd\leq n}$ und ${\displaystyle (q+1)d>n}$. Sei ${\displaystyle {}r:=n-qd}$. Dann ist

${\displaystyle {}qd\leq qd+r<qd+d\,}$

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

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

Im zweiten Fall erfüllen ${\displaystyle {}q=-{\tilde {q}}-1}$ und ${\displaystyle {}r=d-{\tilde {r}}}$ die Bedingungen.
Zur Eindeutigkeit. Sei ${\displaystyle {}qd+r=n={\tilde {q}}d+{\tilde {r}}}$, wobei die Bedingungen jeweils erfüllt seien. Es sei ohne Einschränkung ${\displaystyle {}{\tilde {r}}\geq r}$. Dann gilt ${\displaystyle {}(q-{\tilde {q}})d={\tilde {r}}-r}$. Diese Differenz ist nichtnegativ und kleiner als ${\displaystyle {}d}$, links steht aber ein Vielfaches von ${\displaystyle {}d}$, so dass die Differenz ${\displaystyle {}0}$ sein muss und die beiden Darstellungen überein stimmen.

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

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

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

Beweise den Rekursionssatz für aufspannende Bäume.

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

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.