%Daten zur Institution
%\input{Dozentdaten}
%\renewcommand{\fachbereich}{Fachbereich}
%\renewcommand{\dozent}{Prof. Dr. . }
%Klausurdaten
\renewcommand{\klausurgebiet}{ }
\renewcommand{\klausurtyp}{ }
\renewcommand{\klausurdatum}{ . 20}
\klausurvorspann {\fachbereich} {\klausurdatum} {\dozent} {\klausurgebiet} {\klausurtyp}
%Daten für folgende Punktetabelle
\renewcommand{\aeins}{ 3 }
\renewcommand{\azwei}{ 3 }
\renewcommand{\adrei}{ 6 }
\renewcommand{\avier}{ 2 }
\renewcommand{\afuenf}{ 3 }
\renewcommand{\asechs}{ 4 }
\renewcommand{\asieben}{ 3 }
\renewcommand{\aacht}{ 0 }
\renewcommand{\aneun}{ 3 }
\renewcommand{\azehn}{ 0 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 0 }
\renewcommand{\adreizehn}{ 3 }
\renewcommand{\avierzehn}{ 3 }
\renewcommand{\afuenfzehn}{ 4 }
\renewcommand{\asechzehn}{ 3 }
\renewcommand{\asiebzehn}{ 0 }
\renewcommand{\aachtzehn}{ 1 }
\renewcommand{\aneunzehn}{ 0 }
\renewcommand{\azwanzig}{ 45 }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabelleneunzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabepunkteloesung
{3}
{
Definiere die folgenden\zusatzklammer {kursiv gedruckten} {} {} Begriffe.\aufzaehlungsechs{Die \stichwort {Fakultät} {} einer natürlichen Zahl $n$.
}{Eine\stichwort {linksvollständige} {} Relation
\mavergleichskette
{\vergleichskette
{R}
{ \subseteq }{M \times N}
{ }{}
{ }{}
{ }{}
}{}{}{.}
}{Eine \stichwort {obere Schranke} {} zu einer Teilmenge
\mavergleichskette
{\vergleichskette
{J}
{ \subseteq }{ I}
{ }{}
{ }{}
{ }{}
}{}{}{}in einer\definitionsverweis {geordneten Menge}{}{}
\mathl{(I,\preccurlyeq)}{.}
}{Ein\stichwort {starrer} {} Graph.
}{Die\stichwort {Lapace-Matrix} {} zu einem Multigraphen $G$.
}{Die\stichwort {chromatische Zahl} {} eines Graphen.}
}
{
\aufzaehlungsechs{Unter der Fakultät von $n$ versteht man die Zahl
\mavergleichskettedisp
{\vergleichskette
{n!}
{ \defeq} { n(n-1)(n-2) \cdots 3 \cdot 2 \cdot 1 }
{ } {}
{ } {}
{ } {}
}{}{}{.}}{Die\definitionsverweis {Relation}{}{}
\mavergleichskette
{\vergleichskette
{R}
{ \subseteq }{M \times N}
{ }{}
{ }{}
{ }{}
}{}{}{}heißtlinksvollständig, wenn es zu jedem
\mavergleichskette
{\vergleichskette
{x}
{ \in }{M}
{ }{}
{ }{}
{ }{}
}{}{}{}ein
\mavergleichskette
{\vergleichskette
{y}
{ \in }{N}
{ }{}
{ }{}
{ }{}
}{}{}{}mit
\mavergleichskette
{\vergleichskette
{(x,y)}
{ \in }{R}
{ }{}
{ }{}
{ }{}
}{}{}{}gibt.}{Ein Element
\mathl{x \in I}{} heißt obere Schranke für $J$, wenn
\mavergleichskette
{\vergleichskette
{ y}
{ \preccurlyeq }{x}
{ }{}
{ }{}
{ }{}
}{}{}{}für jedes
\mathl{y \in J}{} gilt.}{Ein\definitionsverweis {Graph}{}{}
\mavergleichskette
{\vergleichskette
{G}
{ = }{(V,E)}
{ }{}
{ }{}
{ }{}
}{}{}{}heißtstarr, wenn die\definitionsverweis {Automorphismengruppe}{}{}von $G$ trivial ist.}{Zu einem\definitionsverweis {Multigraphen}{}{}$G$ versteht man unter derLaplace-Matrix $L$ die Differenz
\mavergleichskettedisp
{\vergleichskette
{L}
{ =} { D-A}
{ } {}
{ } {}
{ } {}
}{}{}{}aus\definitionsverweis {Gradmatrix}{}{}$D$ und\definitionsverweis {Adjazenzmatrix}{}{}$A$.}{Diechromatische Zahleines Graphen ist die minimale Anzahl an Farben, die man für eine\definitionsverweis {zulässige Färbung}{}{}benötigt.}
}
\inputaufgabepunkteloesung
{3}
{
Formuliere die folgenden Sätze.\aufzaehlungdrei{Der Satz über die Anzahl in der Potenzmenge zu einer endlichen Menge.}{Der Satz über die Beschreibung des Durchschnitts von Untergruppen von $\Z$.}{Der\stichwort {Fünf-Farben-Satz} {.}}
}
{
\aufzaehlungdrei{Es sei $M$ eine\definitionsverweis {endliche Menge}{}{}mit $m$ Elementen. Dann besitzt die\definitionsverweis {Potenzmenge}{}{}
\mathl{\mathfrak {P} \, (M )}{} genau $2^m$ Elemente.}{Es seien
\mathl{a_1 , \ldots , a_k}{} ganze Zahlen. Dann ist
\mavergleichskettedisp
{\vergleichskette
{\Z a_1 \cap \Z a_2 \cap \ldots \cap \Z a_k}
{ =} { \Z u}
{ } {}
{ } {}
{ } {}
}{}{}{,}wobei $u$ das \definitionsverweis {kleinste gemeinsame Vielfache}{}{}der
\mathl{a_1 , \ldots , a_k}{} ist.}{Für jeden \definitionsverweis {ebenen Graphen}{}{}besteht eine\definitionsverweis {zulässige Färbung}{}{}mit höchstens fünf Farben.}
}
\inputaufgabepunkteloesung
{6}
{
Beweise den Satz über die Wohldefiniertheit der Anzahl einer endlichen Menge.
}
{
Es seien die bijektiven Abbildungen\maabbdisp {\varphi} { { \{ 1 , \ldots , n \} } } {M} {}und\maabbdisp {\psi} { \{ 1 , \ldots , k \} } {M} {}gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nachAufgabe 3.28 (Mathematik für Anwender (Osnabrück 2023-2024)) (3)wieder bijektiv ist, ist auch\maabbdisp {\psi^{-1} \circ \varphi} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \} } {}bijektiv. Wir müssen also nur die endlichen Standardmengen
\mathl{{ \{ 1 , \ldots , n \} }}{} untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung\maabbdisp {\theta} { { \{ 1 , \ldots , n \} } } { \{ 1 , \ldots , k \} } {}vorliegt, dass dann
\mavergleichskettedisp
{\vergleichskette
{n}
{ =} {k}
{ } {}
{ } {}
{ } {}
}{}{}{}ist. Dies zeigen wir durch Induktion nach $n$. Wenn
\mavergleichskette
{\vergleichskette
{n}
{ = }{ 0}
{ }{}
{ }{}
{ }{}
}{}{}{}ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch
\mavergleichskette
{\vergleichskette
{k}
{ = }{ 0}
{ }{}
{ }{}
{ }{}
}{}{}{.}Es seien nun
\mathl{n,k}{} nicht $0$, so dass sie also jeweils einen Vorgänger haben. Es sei $m$ der Vorgänger von $n$ und $\ell$ der Vorgänger von $k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen
\mavergleichskettedisp
{\vergleichskette
{ z}
{ =} {\theta (n)}
{ \in} { \{ 1 , \ldots , k \} }
{ } {}
{ } {}
}{}{}{.}Dann gibt es nach der Herausnahme von $n$ bzw. $z$ eine bijektive Abbildung\maabbdisp {} { \{ 1 , \ldots , m \} = { \{ 1 , \ldots , n \} } \setminus \{n\} } { \{ 1 , \ldots , k \} \setminus \{z\}} {.}NachLemma 1.2 (Diskrete Mathematik (Osnabrück 2020))gibt es eine bijektive Abbildung zwischen\mathkor {} {\{1 , \ldots , \ell \}} {und} {\{ 1 , \ldots , k \} \setminus \{z\}} {.}Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen\mathkor {} {\{ 1 , \ldots , m \}} {und} {\{1 , \ldots , \ell \}} {.}Nach Induktionsvoraussetzung ist
\mavergleichskette
{\vergleichskette
{m}
{ = }{\ell}
{ }{}
{ }{}
{ }{}
}{}{}{,}also auch
\mavergleichskettedisp
{\vergleichskette
{n}
{ =} {m'}
{ =} {\ell'}
{ =} {k}
{ } {}
}{}{}{.}
}
\inputaufgabepunkteloesung
{2}
{
Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von $10$ Cent begleichen?
}
{
Wir zählen zunächst die Möglichkeiten, mit den $5$- und $10$-Centmünzen die folgenden Beträge darzustellen:
\mathdisp {0 \text{ Cent}: 1 \text{ Möglichkeit}} { , }
\mathdisp {5 \text{ Cent}: 1 \text{ Möglichkeit}} { , }
\mathdisp {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
\mathdisp {6 , 3,1 \text{ Möglichkeiten}} { . }
Diese Möglichkeiten für die Zweier muss man mit den obigen Möglichkeiten multiplizieren, das ergibt insgesamt
\mavergleichskettedisp
{\vergleichskette
{1 \cdot 6 + 1 \cdot 3 + 2\cdot 1}
{ =} { 11}
{ } { }
{ } {}
{ } {}
}{}{}{}Möglichkeiten.
}
\inputaufgabepunkteloesung
{3 (1.5+1.5)}
{
Ein Zug fährt $100$ Kilometer den Rhein abwärts mit einer Geschwindigkeit von $100$ kmh.Auf dem Rhein fahren Schiffe in beide Richtungen, alle mit einer Geschwindigkeit von $20$ kmh, wobei sie zu den gleichgerichteten Schiffen einen konstanten Abstand von $2$ km einhalten. Zu Beginn der Fahrt ist der Zug gleichauf mit zwei Schiffen\zusatzklammer {in beide Richtungen} {} {.}\aufzaehlungzwei {Wie vielen entgegenkommenden Schiffen begegnet der Zug?} {Wie viele Schiffe überholt der Zug?}
}
{
Wir denken uns die Rheinstrecke skaliert von $0$ bis $120$, der Startort ist beim Nullpunkt $0$ und der Zielpunkt des Zuges ist bei $100$. Aufgrund der Anfangsbedingung befinden sich zum Startzeitpunkt Schiffe in beide Richtungen in den Positionen
\mathdisp {0,2,4 , \ldots , 98, 100, 102 , \ldots , 118, 120} { . }
\aufzaehlungzwei {Die entgegenkommenden Schiffe sind die in Gegenrichtung fahrenden Schiffe, die sich zum Startzeitpunkt an den Positionen
\mathl{0}{} bis $120$ befinden \zusatzklammer {das Schiff in der Position $120$ ist nach einer Stunde an der Position $100$ und begegnet zum Endzeitpunkt dem Zug} {} {.}Dies sind insgesamt $61$ Schiffe.} {Die eingeholten Schiffe sind die in gleicher Richtung fahrenden Schiffe, die sich zum Startzeitpunkt an den Positionen
\mathl{0}{} bis $80$ befinden \zusatzklammer {das Schiff in der Position $80$ ist nach einer Stunde an der Position $100$ und wird zum Endzeitpunkt vom Zug eingeholt} {} {.}Dies sind insgesamt $41$ Schiffe.}
}
\inputaufgabepunkteloesung
{4}
{
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\zusatzklammer {die Reihenfolge ist aber egal} {} {,}die beiden Ballstationen \zusatzklammer {Basketballkorb und Medizinball} {} {}sollen aber nicht unmittelbar hintereinander absolviert werden.
Wie viele Möglichkeiten\zusatzklammer {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 \anfuehrung{Holz}{.} Damit gibt es $5$ Stationen. Es gibt
\mavergleichskette
{\vergleichskette
{ \binom { 5 } { 2 }}
{ = }{ 10}
{ }{}
{ }{}
{ }{}
}{}{}{}Möglichkeiten, aus den $5$ Positionen $2$ Positionen auszusuchen, an denen der Basketballkorb bzw. der Medizinball absolviert wird. Darunter gibt es $4$ Möglichkeiten, bei denen beiden Ballstationen direkt hintereinander liegen. Somit gibt es
\mavergleichskette
{\vergleichskette
{10-4}
{ = }{6}
{ }{}
{ }{}
{ }{}
}{}{}{}erlaubte Auswahlen für die Positionen der beiden Ballstationen. Wenn diese festgelegt sind, so gibt es jeweils $2$ Möglichkeiten, welche der beiden Ballstationen an welcher Position durchgeführt wird, es gibt
\mavergleichskette
{\vergleichskette
{3!}
{ = }{6}
{ }{}
{ }{}
{ }{}
}{}{}{}Möglichkeiten, in welcher Reihenfolge die drei anderen Stationen\zusatzklammer {also Trampolin, Laufband und Holz} {} {}abgearbeitet werden, und dann gibt es noch jeweils $2$ Möglichkeiten für die Reihenfolge innerhalb der Holzstation. Insgesamt gibt es also
\mavergleichskettedisp
{\vergleichskette
{6 \cdot 6 \cdot 2 \cdot 2}
{ =} {144}
{ } {}
{ } {}
{ } {}
}{}{}{}erlaubte Reihenfolgen.
}
\inputaufgabepunkteloesung
{3}
{
Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring $R$ durch Induktion über $k$, wobei der Fall
\mavergleichskette
{\vergleichskette
{k}
{ = }{2}
{ }{}
{ }{}
{ }{}
}{}{}{}verwendet werden darf\zusatzklammer {dabei sind
\mathl{n_1 , \ldots , n_k}{} natürliche Zahlen und
\mathl{a_{j,i} \in R}{}} {} {.}
\mavergleichskettealign
{\vergleichskettealign
{ { \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}}
{ } {}
{ } {}
{ } {}
}{}{}{.}
}
{
Es sei die Aussage für ein bestimmtes $k$ bewiesen. Für
\mathl{k+1}{} Faktoren ist dann unter Verwendung der Induktionsvoraussetzung und unter Verwendung des Falles von zwei Faktoren
\mavergleichskettealign
{\vergleichskettealign
{ }
{ { \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) } }
{ } {}
}{}{}{.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung}
\inputaufgabepunkteloesung
{3 (1+1+1)}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Austria States Cities.png} }
\end{center}
\bildtext {} }
\bildlizenz { Austria States Cities.png } {} {Gevin} {Commons} {CC-by-sa 3.0} {}
Die Karte zeigt Österreich mit seinen Bundesländern und den zugehörigen Hauptstädten\zusatzklammer {die Hauptstadt des Bundeslandes Wien ist Wien, Tirol ist ein Bundesland} {} {.}Es sei $M$ die Menge der Bundesländer und sei $R$ die Relation auf $M$, die die Angrenzungsbeziehung\zusatzklammer {Nachbarschaftsbeziehung} {} {}beschreibt. Dabei legen wir fest, dass ein Land auch zu sich selbst benachbart ist.\aufzaehlungdrei{Welche Eigenschaften einer \definitionsverweis {Äquivalenzrelation}{}{}erfüllt diese Relation?}{Bestimme die\definitionsverweis {Faser}{}{}zu Kärnten.}{Gibt es eine Kette $x_1,x_2 , \ldots , x_n$ in $M$ mit
\mathl{x_iRx_{i+1}}{} für alle $i$, bei der jedes Bundesland genau einmal vorkommt?}
}
{
\aufzaehlungdrei{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.}{Die Faser zu Kärnten besteht aus Kärnten, Steiermark, Salzburg, Tirol. }{Das ist möglich: Wien, Niederösterreich, Burgenland, Steiermark, O\-berösterreich, Salzburg, Kärnten, Tirol, Vorarlberg.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung}
\inputaufgabepunkteloesung
{4}
{
Beweise das Lemma von Euklid für ganze Zahlen.
}
{
Wir setzen voraus, dass $a$ kein Vielfaches von $p$ ist\zusatzklammer {andernfalls sind wir fertig} {} {.}Dann müssen wir zeigen, dass $b$ ein Vielfaches von $p$ ist. Unter der gegebenen Voraussetzung sind\mathkor {} {a} {und} {p} {}\definitionsverweis {teilerfremd}{}{.}Nachdem Lemma von Bezoutgibt es ganze Zahlen
\mathl{r,s}{} mit
\mavergleichskettedisp
{\vergleichskette
{ ra +sp}
{ =} {1}
{ } {}
{ } {}
{ } {}
}{}{}{}Da
\mathl{ab}{} ein Vielfaches von $p$ ist, gibt es ein $t$ mit
\mavergleichskettedisp
{\vergleichskette
{ab}
{ =} {tp}
{ } {}
{ } {}
{ } {}
}{}{}{.}Daher ist
\mavergleichskettedisp
{\vergleichskette
{ b}
{ =} { b \cdot 1}
{ =} { b (ra +sp) }
{ =} { ab r + bs p }
{ =} { t p r +bsp}
}{
\vergleichskettefortsetzung
{ =} { p { \left( tr +bs \right) } }
{ } {}
{ } {}
{ } {}
}{}{.}Also ist $b$ ein Vielfaches von $p$.
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung}
\inputaufgabepunkteloesung
{3}
{
Bestimme das inverse Element zu
\mathl{\overline{55}}{} in
\mathl{\Z/(93)}{.}
}
{
Der euklidische Algorithmus liefert
\mavergleichskettedisp
{\vergleichskette
{93}
{ =} { 1 \cdot 55 + 38}
{ } {}
{ } {}
{ } {}
}{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 55}
{ =} { 1 \cdot 38 + 17}
{ } {}
{ } {}
{ } {}
}{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 38}
{ =} { 2 \cdot 17 +4}
{ } {}
{ } {}
{ } {}
}{}{}{,}
\mavergleichskettedisp
{\vergleichskette
{ 17}
{ =} { 4 \cdot 4 +1}
{ } {}
{ } {}
{ } {}
}{}{}{.}Somit ist
\mavergleichskettealign
{\vergleichskettealign
{ 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}
}{
\vergleichskettefortsetzungalign
{ =} { 9 \cdot 55 -13 \cdot 38}
{ =} { 9 \cdot 55 -13 \cdot { \left( 93-55 \right) } }
{ =} { 22 \cdot 55 -13 \cdot 93 }
{ } {}
}{}{.}Daher ist
\mathdisp {22} { }
das inverse Element zu $55$ in
\mathl{\Z/(93)}{.}
}
\inputaufgabepunkteloesung
{3}
{
Es seien\mathkor {} {M} {und} {N} {}\definitionsverweis {endliche Mengen}{}{}mit $m$ bzw. $n$ Elementen und sei\maabbdisp {f} {M} {N} {}eine\definitionsverweis {surjektive Abbildung}{}{.}Wie viele Abbildungen\maabbdisp {s} {N} {M} {}mit
\mavergleichskettedisp
{\vergleichskette
{ f \circ s}
{ =} { \operatorname{Id}_{ N } }
{ } {}
{ } {}
{ } {}
}{}{}{}gibt es?
}
{
Die Elemente aus $N$ seien mit
\mathl{1,2 , \ldots , n}{} bezeichnet. Zu jedem
\mavergleichskette
{\vergleichskette
{ i}
{ \in }{ N}
{ }{}
{ }{}
{ }{}
}{}{}{}sei
\mavergleichskettedisp
{\vergleichskette
{ M_i}
{ =} { { \left\{ x \in M \mid f(x) = i \right\} }}
{ } {}
{ } {}
{ } {}
}{}{}{}und
\mavergleichskettedisp
{\vergleichskette
{m_i}
{ =} { { \# \left( M_i \right) } }
{ =} { { \# \left( { \left\{ x \in M \mid f(x) = i \right\} } \right) }}
{ } {}
{ } {}
}{}{}{}die Anzahl der Elemente aus $M$, die auf $i$ abgebildet werden. Wegen der Surjektivität ist stets
\mavergleichskette
{\vergleichskette
{m_i}
{ \geq }{1}
{ }{}
{ }{}
{ }{}
}{}{}{.}Da
\mavergleichskettedisp
{\vergleichskette
{f \circ s}
{ =} { \operatorname{Id}_{ N } }
{ } {}
{ } {}
{ } {}
}{}{}{}gelten soll, muss
\mavergleichskette
{\vergleichskette
{ s(i) }
{ \in }{ M_i}
{ }{}
{ }{}
{ }{}
}{}{}{} für jedes $i$ gelten. Somit gibt es
\mathdisp {m_1 \cdot m_2 \cdots m_n} { }
Möglichkeiten für solche Abbildungen.
}
\inputaufgabepunkteloesung
{4 (2+2)}
{
Es sei\maabb {\varphi} {G} {H} {}ein\definitionsverweis {Graphhom*omorphismus}{}{.}\aufzaehlungzwei {Es sei $\varphi$ injektiv. Zeige, dass für den \definitionsverweis {Grad}{}{}die Abschätzung
\mavergleichskettedisp
{\vergleichskette
{ d(P)}
{ \leq} { d( \varphi(P))}
{ } {}
{ } {}
{ } {}
}{}{}{}für jeden Punkt
\mavergleichskette
{\vergleichskette
{P}
{ \in }{G}
{ }{}
{ }{}
{ }{}
}{}{}{}gilt.} {Wie sieht es aus, wenn $\varphi$ nicht injektiv ist?}
}
{
\aufzaehlungzwei {Es seien $v_1 , \ldots , v_n$ die an $P$ anliegenden Punkte, also
\mavergleichskette
{\vergleichskette
{d(P)}
{ = }{n}
{ }{}
{ }{}
{ }{}
}{}{}{.}Diese werden auf verschiedene Punkte
\mathl{\varphi(v_i)}{} abgebildet und es ist stets
\mathl{\varphi(P) \varphi(v_i)}{} eine Kante von $H$. Also liegen an $\varphi(P)$ zumindest $n$ Kanten an.} {Ohne die Voraussetzung injektiv ist die Aussage aus (1) nicht richtig. Betrachten wir den linearen Graphen
\mathl{1 ,2,3}{,} also mit den zwei Kanten\mathkor {} {\{1,2\}} {und} {\{2,3\}} {,}und die Abbildung auf den linearen Graphen $a,b$, also mit der Kante
\mathl{\{a,b\}}{,} der\mathkor {} {1} {und} {3} {}auf $a$ und $2$ auf $b$ abbildet. Da Kanten auf Kanten gehen, liegt ein Graphhom*omorphismus vor. Der Grad von $2$ ist aber gleich $2$, während der Grad von $b$ gleich $1$ ist.}
}
\inputaufgabepunkteloesung
{3 (1.5+1.5)}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Clubagroup official insignia.jpg} }
\end{center}
\bildtext {} }
\bildlizenz { Clubagroup official insignia.jpg } {} {Skull and Bones somewhat inspired} {Commons} {CC-by-sa 3.0} {}
Wir betrachten den \definitionsverweis {Spielzuggraphen}{}{}zum Läufer beim Schach auf einem $3 \times 3$-Brett wie abgebildet.\aufzaehlungzwei {Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer\definitionsverweis {bipartit}{}{}ist.} {Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufernicht bipartit ist.}
}
{
\aufzaehlungzwei {Die beiden weißen horizontalen Felder \zusatzklammer {links bzw. rechts} {} {} und die beiden weißen vertikalen Felder \zusatzklammer {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.} {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 \definitionsverweis {Kreis}{}{}der Länge $3$, was es nach Satz 20.8 (Diskrete Mathematik (Osnabrück 2020))in einem bipartiten Graphen nicht gibt.}
}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung}
\inputaufgabepunkteloesung
{1}
{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{\bildeinlesung {Dürer graph hamiltonicity.svg} }
\end{center}
\bildtext {} }
\bildlizenz { Dürer graph hamiltonicity.svg } {} {David Eppstein} {Commons} {CC0 1.0} {}
Begründe, dass der abgebildete Graph\definitionsverweis {hamiltonsch}{}{}ist.
}
{Dürergraph/Hamiltonsch/Aufgabe/Lösung}
\inputaufgabepunkteloesung
{0}
{
}
{/Aufgabe/Lösung}
