Kurs:Diskrete Mathematik/15/Klausur mit Lösungen/latex
%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}{ 2 }
\renewcommand{\avier}{ 4 }
\renewcommand{\afuenf}{ 4 }
\renewcommand{\asechs}{ 2 }
\renewcommand{\asieben}{ 6 }
\renewcommand{\aacht}{ 2 }
\renewcommand{\aneun}{ 7 }
\renewcommand{\azehn}{ 2 }
\renewcommand{\aelf}{ 4 }
\renewcommand{\azwoelf}{ 2 }
\renewcommand{\adreizehn}{ 0 }
\renewcommand{\avierzehn}{ 0 }
\renewcommand{\afuenfzehn}{ 0 }
\renewcommand{\asechzehn}{ 0 }
\renewcommand{\asiebzehn}{ 10 }
\renewcommand{\aachtzehn}{ 0 }
\renewcommand{\aneunzehn}{ 0 }
\renewcommand{\azwanzig}{ 51 }
\renewcommand{\aeinundzwanzig}{ }
\renewcommand{\azweiundzwanzig}{ }
\renewcommand{\adreiundzwanzig}{ }
\renewcommand{\avierundzwanzig}{ }
\renewcommand{\afuenfundzwanzig}{ }
\renewcommand{\asechsundzwanzig}{ }
\punktetabelleneunzehn
\klausurnote
\newpage
\setcounter{section}{0}
\inputaufgabeklausurloesung
{3}
{
Definiere die folgenden \zusatzklammer {kursiv gedruckten} {} {} Begriffe. \aufzaehlungsechs{Die \stichwort {Kommutativität} {} einer Verknüpfung \maabbdisp {\circ} {M \times M} {M } {.}
}{Ein
\stichwort {Atom} {}
\mavergleichskette
{\vergleichskette
{ a
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einer
\definitionsverweis {geordneten Menge}{}{}
\mathl{(M, \preccurlyeq)}{} mit einem
\definitionsverweis {kleinsten Element}{}{}
$0$.
}{Ein
\stichwort {Ideal} {}
\mathl{{\mathfrak a} \subseteq R}{} in einem
\definitionsverweis {kommutativen Ring}{}{}
$R$.
}{Zwei
\stichwort {isomorphe} {}
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Der
\stichwort {Quotientengraph} {}
zu einer
\definitionsverweis {Äquivalenzrelation}{}{}
$\sim$ auf einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{ G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Eine
\stichwort {maximale} {}
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{ P
}
{ \subseteq }{ E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in einem
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{ G
}
{ = }{ (V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
{
\aufzaehlungsechs{Eine
\definitionsverweis {Verknüpfung}{}{}
\maabbeledisp {\circ} {M \times M} {M
} {(x,y)} {x \circ y
} {,}
heißt kommutativ, wenn für alle
\mathl{x,y \in M}{} die Gleichheit
\mavergleichskettedisp
{\vergleichskette
{ x \circ y
}
{ =} { y \circ x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gilt.
}{Ein Element
\mavergleichskette
{\vergleichskette
{a
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
Atom,
wenn
\mavergleichskette
{\vergleichskette
{a
}
{ \neq }{0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist und die Beziehung
\mavergleichskette
{\vergleichskette
{x
}
{ \preccurlyeq }{a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nur für
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gilt.
}{Ein Ideal ist eine nichtleere Teilmenge ${\mathfrak a} \subseteq R$, für die die beiden folgenden Bedingungen erfüllt sind:
\aufzaehlungzwei {Für alle
\mathl{a,b \in {\mathfrak a}}{} ist auch
\mathl{a+b \in {\mathfrak a}}{.}
} {Für alle
\mathl{a \in {\mathfrak a}}{} und
\mathl{r \in R}{} ist auch
\mathl{ra \in {\mathfrak a}}{.} }
}{Die beiden
\definitionsverweis {Graphen}{}{}
\mavergleichskette
{\vergleichskette
{G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{H
}
{ = }{ (W,F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißen
isomorph,
wenn es einen
\definitionsverweis {Graphisomorphismus}{}{}
\maabb {\varphi} {G} {H
} {}
gibt.
}{Der
Quotientengraph
ist die
\definitionsverweis {Quotientenmenge}{}{}
$V/\sim$, versehen mit der
\definitionsverweis {Bildgraphenstruktur}{}{}
zur
\definitionsverweis {kanonischen Abbildung}{}{}
\maabbdisp {} { V } { V/\sim
} {.}
}{Die
\definitionsverweis {Paarung}{}{}
\mavergleichskette
{\vergleichskette
{ P
}
{ \subseteq }{ E
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
heißt
maximal,
wenn jedes $P'$ mit
\mavergleichskette
{\vergleichskette
{ P
}
{ \subset }{ P'
}
{ \subseteq }{ E
}
{ }{
}
{ }{
}
}
{}{}{}
keine Paarung ist.
}
}
\inputaufgabeklausurloesung
{3}
{
Formuliere die folgenden Sätze. \aufzaehlungdrei{Der Satz über die atomare Darstellung in einem booleschen Verband.}{Der Satz über die Anzahl der surjektiven Abbildungen mit Binomialkoeffizienten.}{Der Satz über die Potenzen der Adjazenzmatrix.}
}
{
\aufzaehlungdrei{In einem endlichen
\definitionsverweis {booleschen Verband}{}{}
besitzt jedes Element
\mavergleichskette
{\vergleichskette
{ x
}
{ \in }{ B
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine eindeutige Darstellung der Form
\mavergleichskettedisp
{\vergleichskette
{ x
}
{ =} { a_1 \sqcup \ldots \sqcup a_n
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\definitionsverweis {Atomen}{}{}
$a_j$.}{Es sei $A$ eine $n$-elementige Menge und $B$ eine $k$-elementige Menge. Dann ist die Anzahl der
\definitionsverweis {surjektiven Abbildungen}{}{}
von $A$ nach $B$ gleich
\mathdisp {\sum_{j = 0}^k (-1)^{k-j} \binom { k } { j } j^n} { . }
}{Es sei
\mavergleichskette
{\vergleichskette
{ G
}
{ = }{(V,E)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein
\definitionsverweis {Graph}{}{}
mit zugehöriger
\definitionsverweis {Adjazenzmatrix}{}{}
$A$. Dann ist die Anzahl der
\definitionsverweis {Wege}{}{}
von
\mathkor {} {u} {nach} {v} {}
der
\definitionsverweis {Länge}{}{}
$\ell$ gleich dem Eintrag an der Stelle
\mathl{(u,v)}{} zur
\definitionsverweis {Matrixpotenz}{}{}
$A^\ell$.}
}
\inputaufgabeklausurloesung
{2}
{
$\,$
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungJPG {Mercedes Benz Atego 1624 container truck} {JPG} }
\end{center}
\bildtext {} }
\bildlizenz { Mercedes Benz Atego 1624 container truck.JPG } {} {High Contrast} {Commons} {CC-ba-sa 3.0} {}
Die Absetzmulde ist voll mit Schutt und soll durch eine leere Mulde ersetzt werden, die das Absetzkipperfahrzeug bringt, das auch die volle Mulde mitnehmen soll. Auf dem Fahrzeug und auf dem Garagenvorplatz, wo die volle Mulde steht, ist nur Platz für eine Mulde. Dafür kann die Straße als Zwischenablage genutzt werden. Wie viele Ladevorgänge sind vor Ort nötig, bis der Gesamtaustausch vollständig abgeschlossen ist?
}
{
\aufzaehlungsechs{Leere Mulde auf dem Straßenplatz $A$ abladen. }{Volle Mulde auf Fahrzeug hochladen. }{Volle Mulde auf dem Straßenplatz $B$ abladen. }{Leere Mulde auf Fahrzeug hochladen. }{Leere Mulde auf den Garagenvorplatz abladen. }{Volle Mulde auf Fahrzeug hochladen. } Es sind also sechs Ladevorgänge nötig.
}
\inputaufgabeklausurloesung
{4}
{
Es sei $M$ eine $n$-elementige Menge. Zeige durch Induktion über $k$, dass die Anzahl der $k$-elementigen Teilmengen von $M$ gleich dem
\definitionsverweis {Binomialkoeffizienten}{}{}
\mathdisp {\binom { n } { k }} { }
ist.
}
{
Es sei $n$ fixiert. Bei
\mavergleichskette
{\vergleichskette
{k
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es nur die leere Menge, was mit dem Binomialkoeffizienten
\mavergleichskettedisp
{\vergleichskette
{ \binom { n } { 0 }
}
{ =} { 1
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
übereinstimmt. Es sei die Aussage also für ein $k$ zwischen
\mathkor {} {0} {und} {n-1} {}
schon bewiesen. Jeder $k$-elementigen Teilmenge $S$ von $M$ und jedem der $n-k$ Elemente $x$ aus
\mathl{M \setminus S}{} kann man die
\mathl{k+1}{-}elementige Menge
\mavergleichskettedisp
{\vergleichskette
{T
}
{ =} { S \cup \{x\}
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
zuordnen. Dabei wird jede
\mathl{k+1}{-}elementige Menge $T$ erreicht, und zwar $k+1$-fach, da man ja aus $T$ jedes der $k+1$ Elemente herausnehmen kann. Zwischen der Anzahl $A_k$ der $k$-elementigen Teilmengen von $M$ und der Anzahl $A_{k+1}$ der $k+1$-elementigen Teilmengen von $M$ besteht also der Zusammenhang
\mavergleichskettedisp
{\vergleichskette
{A_{k+1} \cdot (k+1)
}
{ =} { A_k \cdot (n-k)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Unter Verwendung der Induktionsvoraussetzung ist daher
\mavergleichskettealign
{\vergleichskettealign
{A_{k+1}
}
{ =} { { \frac{ n-k }{ k+1 } } A_k
}
{ =} { { \frac{ n-k }{ k+1 } } \binom { n } { k }
}
{ =} { { \frac{ n-k }{ k+1 } } \cdot { \frac{ n (n-1) \cdots (n-k+1) }{ k! } }
}
{ =} { { \frac{ n (n-1) \cdots (n-k+1)(n-k) }{ (k+1)! } }
}
}
{
\vergleichskettefortsetzungalign
{ =} { \binom { n } { k+1 }
}
{ } {}
{ } {}
{ } {}
}
{}{}
}
\inputaufgabeklausurloesung
{4}
{
Es sei $M$ eine beliebige Menge. Zeige, dass es keine \definitionsverweis {surjektive Abbildung}{}{} von $M$ in die \definitionsverweis {Potenzmenge}{}{} $\mathfrak {P} \, (M )$ geben kann.
}
{
Wir nehmen an, dass es eine surjektive Abbildung
\maabbeledisp {F} { M } { \mathfrak {P} \, ( M ) } { x } { F(x) } {,}
gibt, und müssen dies zu einem Widerspruch führen. Dazu betrachten wir
\mavergleichskettedisp
{\vergleichskette
{ T
}
{ =} { { \left\{ x \in M \mid x \notin F(x) \right\} }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Da dies eine Teilmenge von $M$ ist, muss es wegen der Surjektivität ein
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
geben mit
\mavergleichskettedisp
{\vergleichskette
{ F(y)
}
{ =} { T
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es gibt nun zwei Fälle, nämlich
\mathkor {} {y \in F(y)} {oder} {y \not\in F(y)} {.} Im ersten Fall ist also
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und damit, nach der Definition von $T$, auch
\mavergleichskette
{\vergleichskette
{y
}
{ \notin }{ F(y)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
Widerspruch. Im zweiten Fall ist, wieder aufgrund der Definition von $T$,
\mavergleichskette
{\vergleichskette
{y
}
{ \in }{ T
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
und das ist ebenfalls ein Widerspruch.
}
\inputaufgabeklausurloesung
{2}
{
Berechne
\mathdisp {(x+ { \mathrm i} y)^n} { . }
}
{
Nach
dem binomischen Lehrsatz
ist
\mavergleichskettealign
{\vergleichskettealign
{ (x+ { \mathrm i} y)^n
}
{ =} { \sum_{k = 0}^n \binom { n } { k } x^{n-k} { \mathrm i}^k y^k
}
{ =} { \sum_{ k \leq n \text{ gerade} }(-1)^{k/2} \binom { n } { k } x^{n-k} y^k + { \mathrm i} { \left( \sum_{ k \leq n \text{ ungerade} } (-1)^{(k-1)/2} \binom { n } { k } x^{n-k} y^k \right) }
}
{ } {
}
{ } {
}
}
{}
{}{.}
}
\inputaufgabeklausurloesung
{6 (3+3)}
{
Wir betrachten eine Rekursionsvorschrift, die zu einem Zahlendreieck \zusatzklammer {analog zum Pascalschen Dreieck} {} {} führt. In der ersten Zeile steht zentral die $256$, links und rechts davon stehen unendlich viele $1$ \zusatzklammer {die nicht aufgeführt werden müssen} {} {.} Die jeweils nächste Zeile entsteht, indem man von zwei benachbarten Zahlen der Vorgängerzeile das \definitionsverweis {geometrische Mittel}{}{} nimmt und das Ergebnis darunter in der neuen Zeile platziert. \aufzaehlungzwei {Bestimme die ersten Zeilen dieses Zahlendreiecks, bis sämtliche Einträge kleiner als $6$ sind. } {Welche Eigenschaft gilt in jeder Zeile? Warum? }
}
{
\aufzaehlungzwei {Es ergibt sich das folgende Schema.
\mathdisp {\begin{matrix} & & & & & 256 & & & & & \\ & & & & 16 & & 16 & & & & \\ & & & 4 & & 16 & & 4 & & \\ & & 2 & & 8 & & 8 & & 2 & & \\ & \sqrt{2} & & 4 & & 8 & & 4 & & \sqrt{2} & \\ 2^{1/4} & & 2 \cdot 2^{1/4} & & 4 \sqrt{2} & & 4 \sqrt{2} & & 2 \cdot 2^{1/4} & & 2^{1/4} \end{matrix}} { }
Wegen
\mavergleichskettedisp
{\vergleichskette
{ (4 \sqrt{2} )^2
}
{ =} { 32
}
{ \leq} { 6^2
}
{ } {
}
{ } {
}
}
{}{}{}
sind wir fertig.
} {In jeder Zeile ist das Produkt über alle Zahlen gleich $256$. Dies beweist man durch Induktion über den Zeilenindex. In der Startzeile ist das richtig
\zusatzklammer {die nicht hingeschriebenen Zahlen sind $1$} {} {.}
Es sei also das Produkt der Zahlen in einer Zeile gleich $256$. Jede Zahl dieser Zeile geht zweifach in die folgende Zeile ein, einmal als Beitrag zum geometrischen Mittel mit der linken Zahl und einmal als Beitrag zum geometrischen Mittel mit der rechten Zahl. Dabei geht wegen
\mavergleichskette
{\vergleichskette
{ \sqrt{ab}
}
{ = }{ \sqrt{a} \sqrt{b}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
jeweils die Quadratwurzel ein. Das Gesamtprodukt bleibt dabei erhalten.
}
}
\inputaufgabeklausurloesung
{2}
{
\aufzaehlungvier{Skizziere vier Geraden in der Ebene, die sich insgesamt in genau drei Punkten schneiden. }{Skizziere vier Geraden in der Ebene, die sich in keinem Punkt schneiden. }{Skizziere vier Geraden in der Ebene, die sich in einem Punkt schneiden. }{Skizziere vier Geraden in der Ebene, die sich insgesamt in sechs Punkten schneiden. }
}
{
\aufzaehlungvier{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungpng {4Geraden3Schnittpunkte} {png} }
\end{center}
\bildtext {} }
\bildlizenz { 4Geraden3Schnittpunkte.png } {} {Mgausmann} {Commons} {CC-by-sa 4.0} {}
$\,$
}{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungpng {4GeradenKeinSchnittpunkt} {png} }
\end{center}
\bildtext {} }
\bildlizenz { 4GeradenKeinSchnittpunkt.png } {} {Mgausmann} {Commons} {CC-by-sa 4.0} {}
$\,$
}{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungpng {4Geraden1Schnittpunkt} {png} }
\end{center}
\bildtext {} }
\bildlizenz { 4Geraden1Schnittpunkt.png } {} {Mgausmann} {Commons} {CC-by-sa 4.0} {}
$\,$
}{
\bild{ \begin{center}
\includegraphics[width=5.5cm]{ \bildeinlesungpng {4Geraden6Schnittpunkte} {png} }
\end{center}
\bildtext {} }
\bildlizenz { 4Geraden6Schnittpunkte.png } {} {Mgausmann} {Commons} {CC-by-sa 4.0} {}
$\,$ }
}
\inputaufgabeklausurloesung
{7}
{
Beweise das \stichwort {allgemeine Distributivgesetz} {} für einen kommutativen Halbring.
}
{
Wir machen eine Doppelinduktion nach $r$ und nach $s$. D.h. wir beweisen die Aussage für jedes feste $r$ durch Induktion nach $s$
\zusatzklammer {innere Induktion} {} {}
und erhöhen dann in einem eigenen Induktionsdurchgang $r$
\zusatzklammer {äußere Induktion} {} {.}
Bei
\mavergleichskette
{\vergleichskette
{r
}
{ = }{ 0
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist nichts zu zeigen, da dann die Summen links und rechts leer sind, also gleich $0$. Es sei also
\mavergleichskette
{\vergleichskette
{r
}
{ = }{ 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
sodass der linke Faktor einfach eine fixierte Zahl
\mavergleichskette
{\vergleichskette
{a
}
{ = }{ a_1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist. Wir wollen die Aussage in dieser Situation für beliebiges $s$ zeigen. Bei
\mavergleichskette
{\vergleichskette
{s
}
{ = }{ 0, 1
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist die Aussage klar. Es sei die Aussage nun für ein
\mavergleichskettedisp
{\vergleichskette
{s
}
{ \geq} {2
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
schon bewiesen. Dann ist
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ a \cdot { \left( b_1 + \cdots + b_s + b_{s+1} \right) }
}
{ =} { a \cdot { \left( { \left( b_1 + \cdots + b_s \right) } + b_{s+1} \right) }
}
{ =} { a \cdot { \left( b_1 + \cdots + b_s \right) } + a b_{s+1}
}
{ =} { { \left( \sum_{k = 1}^s ab_k \right) } + ab_{s+1}
}
{ =} { \sum_{k = 1}^{s+1} ab_k
}
}
{}
{}{}
nach dem Distributivgesetz und der Induktionsvoraussetzung.
Es sei die Aussage nun für ein festes $r$ und jedes $s$ bewiesen. Dann ist wieder mit dem Distributivgesetz und der Induktionsvoraussetzung
\mavergleichskettealignhandlinks
{\vergleichskettealignhandlinks
{ { \left( \sum_{i = 1}^{r+1} a_i \right) } \cdot { \left( \sum_{k = 1}^s b_k \right) }
}
{ =} { { \left( { \left( \sum_{i = 1}^{r} a_i \right) } +a_{r+1} \right) } \cdot { \left( \sum_{k = 1}^s b_k \right) }
}
{ =} { { \left( \sum_{i = 1}^{r} a_i \right) } \cdot { \left( \sum_{k = 1}^s b_k \right) } +a_{r+1} \cdot { \left( \sum_{k = 1}^s b_k \right) }
}
{ =} { \sum_{ 1 \leq i \leq r,\, 1 \leq k \leq s } a_ib_k + \sum_{k = 1}^s a_{r+1} b_k
}
{ =} { \sum_{ 1 \leq i \leq r+1,\, 1 \leq k \leq s } a_ib_k
}
}
{}
{}{.}
}
\inputaufgabeklausurloesung
{2}
{
Berechne
\mathdisp {(-x^2+x-1)^3} { . }
}
{
Es ist
\mavergleichskettealign
{\vergleichskettealign
{ (-x^2+x-1)^3
}
{ =} { (-x^2+x-1) (-x^2+x-1)^2
}
{ =} { (-x^2+x-1) (x^4-2 x^3 +3x^2 -2 x+1)
}
{ =} { -x^6 +3 x^5 -6 x^4 +7 x^3 -6x^2+ 3 x - 1
}
{ } {
}
}
{}
{}{}
}
\inputaufgabeklausurloesung
{4}
{
Zeige, dass es zu ganzen Zahlen $d,n$ mit $d>0$ eindeutig bestimmte ganze Zahlen $k,s$ mit
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { k d+s
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
und mit
\mavergleichskettedisp
{\vergleichskette
{ - { \frac{ d }{ 2 } }
}
{ <} { s
}
{ \leq} { { \frac{ d }{ 2 } }
}
{ } {
}
{ } {
}
}
{}{}{}
gibt.
}
{
Aufgrund der Division mit Rest in $\Z$ gibt es eindeutig bestimmte ganze Zahlen $q$ und $r$ mit
\mavergleichskettedisp
{\vergleichskette
{ 0
}
{ \leq} { r
}
{ <} { d
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { qd+r
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Bei
\mavergleichskettedisp
{\vergleichskette
{r
}
{ \leq} { { \frac{ d }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist die Existenz bewiesen. Bei
\mavergleichskettedisp
{\vergleichskette
{r
}
{ >} { { \frac{ d }{ 2 } }
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
setzt man
\mavergleichskettedisp
{\vergleichskette
{s
}
{ \defeq} { r-d
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Es ist dann
\mavergleichskettedisp
{\vergleichskette
{0
}
{ >} { s
}
{ =} { r-d
}
{ >} { { \frac{ d }{ 2 } } -d
}
{ =} { - { \frac{ d }{ 2 } }
}
}
{}{}{}
und
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} { qd+r
}
{ =} { (q+1) d+r-d
}
{ =} { (q+1) d+s
}
{ } {
}
}
{}{}{}
ergibt die Existenz. Aus zwei Darstellungen
\mavergleichskettedisp
{\vergleichskette
{kd+s
}
{ =} { n
}
{ =} {\ell d +t
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskette
{\vergleichskette
{s
}
{ \geq }{ t
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ergibt sich
\mavergleichskettedisp
{\vergleichskette
{0
}
{ =} { (k- \ell)d +s-t
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit
\mavergleichskettedisp
{\vergleichskette
{0
}
{ \leq} {s-t
}
{ <} { d
}
{ } {
}
{ } {
}
}
{}{}{}
und die Eindeutigkeit in der Division mit Rest sichert die Eindeutigkeit in der vorliegenden Form.
}
\inputaufgabeklausurloesung
{2}
{
Zeige, dass die
\definitionsverweis {Relation}{}{}
auf
\mathl{\N \times \N}{,} die durch
\mathdisp {(a,b) \sim (c,d), \text{ falls } a+d = b+c} { , }
festgelegt ist, eine
\definitionsverweis {Äquivalenzrelation}{}{}
ist.
}
{
\aufzaehlungdrei{Wegen
\mavergleichskette
{\vergleichskette
{ a+b
}
{ = }{b+a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskette
{\vergleichskette
{(a,b)
}
{ \sim }{(a,b)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die Relation ist also reflexiv.
}{Die Symmetrie folgt daraus, dass aus
\mavergleichskette
{\vergleichskette
{a+d
}
{ = }{b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
sofort
\mavergleichskette
{\vergleichskette
{c+b
}
{ = }{ d+a
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt.
}{Zum Nachweis der Transitivität sei
\mathkor {} {(a,b) \sim (c,d)} {und} {(c,d) \sim (e,f)} {,}
also
\mavergleichskette
{\vergleichskette
{a+d
}
{ = }{b+c
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ c +f
}
{ = }{ d+e
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Dann ist
\mavergleichskettedisp
{\vergleichskette
{ a+f+c
}
{ =} { a+d+e
}
{ =} {b+e+c
}
{ } {
}
{ } {
}
}
{}{}{.}
Aufgrund
der Abziehregel
ist dann
\mavergleichskettedisp
{\vergleichskette
{ a+f
}
{ =} {b+e
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{,}
und dies bedeutet
\mavergleichskette
{\vergleichskette
{(a,b)
}
{ \sim }{(e,f)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
}
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{10}
{
Beweise den Charakterisierungssatz für eulersche Graphen.
}
{
Von (1) nach (2) ist klar, da bei einen geschlossenen Eulerzug jeder Knotenpunkt genau so oft besucht wie verlassen wird.
Von (2) nach (3). Wir führen Induktion über die Anzahl der Kanten. Da der Graph zusammenhängend ist, handelt es sich um einen isolierten Punkt oder aber jeder Knoten besitzt einen Grad von zumindest $2$. Deshalb muss es in $G$ einen
\definitionsverweis {Kreis}{}{}
$K$ geben. Man kann ja inn einem beliebigen Punkt starten und von diesem Punkt ausgehend nach und nach einen Kantenzug konstruieren. Wenn der Kantenzug in einen Punkt hineingeht, so kann man den Kantenzug fortsetzen, da zumindest zwei Kanten in dem Punkt zusammenlaufen. Wenn erstmal ein schon erreichter Punkt erneut auftaucht, ist der Kreis fertig, die \anfuehrung{Vorperiode}{} kann man außer Acht lassen. Es seien $F$ die Kanten des Kreises und wir betrachten den neuen Graphen
\mavergleichskette
{\vergleichskette
{G'
}
{ = }{ (V, E \setminus F)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
Wenn ein Punkt aus $V$ zu einer Kante aus $F$ inzident ist, so reduziert sich der Grad in diesem Knoten um $2$, da ja jeder Punkt in einem Kreis inzident zu zwei Kanten ist. Wenn ein Punkt im Kreis nicht aufgerufen wird, so ändert sich der Grad nicht. In jedem Fall besitzt in $G'$ jeder Punkt wieder einen geraden Grad. Der neue Graph muss nicht mehr zusammenhängend sein, allerdings erfüllen die einzelnen
\definitionsverweis {Zusammenhangskomponenten}{}{}
von $G'$ wieder die Voraussetzung, dass sämtliche Grade gerade sind. Nach Induktionsvoraussetzung besitzen die Zusammenhangskomponenten jeweils eine Darstellung als Vereinigung mit kantendisjunkten Kreisen. Also besitzt $G'$ eine Darstellung als Vereinigung mit kantendisjunkten Kreisen und zusammen mit $K$ ergibt sich eine Darstellung von $G$ als Vereinigung mit kantendisjunkten Kreisen.
Von (3) nach (1). Es seien
\mavergleichskette
{\vergleichskette
{K_j
}
{ = }{ (V_j,E_j)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{j
}
{ \in }{ J
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die beteiligten kantendisjunkten Kreise, die $G$ überdecken. Wir konstruieren induktiv Kantenzüge, die für zunehmend größere Vereinigungen dieser Kreise einen Eulerzug darstellen. Einen einzelnen Kreis kann man unmittelbar als einen Eulerzug für diesen Kreis auffassen. Es sei nun vorausgesetzt, dass man $s$ Kreise, die wir als $K_1 , \ldots , K_s$ durchnummerieren, derart gefunden hat, dass es einen Eulerzug für
\mavergleichskettedisp
{\vergleichskette
{G_s
}
{ =} { \bigcup_{j = 1}^s K_j
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
gibt. Bei
\mavergleichskette
{\vergleichskette
{s
}
{ < }{ r
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es aufgrund des Zusammenhangs des Graphen einen weiteren Kreis, den wir $K_{s+1}$ nennen, der einen gemeinsamen Knotenpunkt mit $G_s$ hat, sagen wir $u$. Dann erhält man aus dem Eulerzug für $G_s$ einen Eulerzug für
\mavergleichskette
{\vergleichskette
{ G_{s+1}
}
{ = }{ G_{s} \cup K_{s+1}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
indem man, wenn der Eulerzug den Punkt $u$ erreicht, in den Kreis $K_{s+1}$ abbiegt, diesen einmal durchläuft und danach an der Stelle $u$ den alten Eulerzug fortsetzt. Da $K_{s+1}$ kantendisjunkt zu $G_s$ ist, entsteht dabei wieder ein Eulerzug.
}
\inputaufgabeklausurloesung
{0}
{
}
{ }
\inputaufgabeklausurloesung
{0}
{
}
{ }