Kurs:Diskrete Mathematik/25/Klausur mit Lösungen

Aufgabe	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	${}\sum$
Punkte	3	3	3	4	3	2	4	3	3	8	6	4	3	2	7	6	64

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Reflexivität einer Relation ${}R$ auf einer Menge ${}M$.
2. Das kleinste gemeinsame Vielfache von natürlichen Zahlen

   $a_{1},\ldots ,a_{n}.$

3. Die kanonische Projektion zu einer Äquivalenzrelation ${}\sim$ auf einer Menge ${}M$.
4. Der Restgraph ${}G\setminus F$ eines Graphen  ${}G=(V,E)$  zu einer Teilmenge  ${}F\subseteq E$  der Kantenmenge.
5. Die Zusammenhangskomponente zu einem Punkt  ${}v\in V$  in einem Graphen  ${}G=(V,E)$. 
6. Eine Knotenüberdeckung in einem Graphen  ${}G=(V,E)$. 

Lösung

1. Die Relation ${}R$ heißt reflexiv, wenn ${}xRx$ für alle ${}x\in M$ gilt.
2. Eine natürliche Zahl ${}b$ ist das kleinste gemeinsame Vielfache dieser Zahlen, wenn ${}b$ ein gemeinsames Vielfaches der ${}a_{i}$ ist und wenn jedes gemeinsame Vielfache der Zahlen ein Vielfaches von ${}b$ ist.
3. Man nennt die Abbildung

   $q\colon M\longrightarrow M/\sim ,\,x\longmapsto [x],$

   die kanonische Projektion.

4. Der Restgraph ${}G\setminus F$ ist derjenige Graph, dessen Punktemenge ${}V$ ist und dessen Kantenmenge aus ${}E\setminus F$ besteht.
5. Die Zusammenhangskomponente von ${}v$ ist

   ${}Z(v)=\left\{u\in V\mid {\text{es gibt einen Weg, der }}u{\text{ und }}v{\text{ verbindet}}\right\}\,.$

6. Eine Knotenüberdeckung ist eine Teilmenge  ${}W\subseteq V$  mit der Eigenschaft, dass jede Kante mindestens einen Knoten aus ${}W$ trifft.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Multinomialsatz für einen kommutativen Halbring.
2. Der Satz über die Anzahl der surjektiven Abbildungen mit Potenzprodukten.
3. Der Vier-Farben-Satz.

Lösung

1. Es sei ${}R$ ein kommutativer Halbring und seien  ${}x_{1},\ldots ,x_{k}\in R$  Elemente und  ${}n\in \mathbb {N}$.  Dann ist

   ${}{\left(x_{1}+\cdots +x_{k}\right)}^{n}=\sum _{r_{1}+\cdots +r_{k}=n}{\binom {n}{r_{1},\dotsc ,r_{k}}}x_{1}^{r_{1}}\cdots x_{k}^{r_{k}}\,.$

2. Es sei ${}A$ eine ${}n$-elementige Menge und ${}B$ eine ${}k$-elementige Menge. Dann ist die Anzahl der surjektiven Abbildungen von ${}A$ nach ${}B$ gleich

   $\sum _{(a_{1},\ldots ,a_{k}):\,a_{1}+a_{2}+\cdots +a_{k}=n,\,a_{j}\geq 1}1^{a_{1}}2^{a_{2}}\cdots k^{a_{k}}.$

3. Für jeden ebenen Graphen besteht eine zulässige Färbung mit höchstens vier Farben.

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

Bei einer Fußballweltmeisterschaft werden in der Runde der letzten vier die Plätze ${}1,2,3,4$ nach folgendem Modus bestimmt: Es gibt zwei Halbfinals, deren Gewinner das Finale und deren Verlierer das Spiel um Platz ${}3$ bestreiten. Von einer solchen Runde seien die Mannschaften ${}A,B,C,D$ und die Ergebnisse der insgesamt vier Spiele bekannt, aber nicht die Rolle der Spiele.

1. Welche Information über die Platzierung kann man stets aus den Daten erschließen?
2. Unter welcher Bedingung kann man die Rolle aller Spiele erschließen,
3. unter welcher nicht?

Lösung

1. Es gibt genau eine Mannschaft, die zweimal gewinnt, diese ist Weltmeister, und genau eine Mannschaft, die zweimal verliert, diese ist Vierter. Die beiden anderen Mannschaften gewinnen einmal und verlieren einmal und sind Zweiter oder Dritter.
2. Wenn der Erste gegen den Vierten (die ja beide bekannt sind) spielt, so muss dieses Spiel ein Hauptfinale sein. Das komplementäre Spiel ist ebenfalls ein Halbfinale, das andere Spiel des Ersten muss das Finale und das andere Spiel des Vierten muss das Spiel um Platz drei sein. Somit sind alle Platzierungen bekannt.
3. Wenn der Erste nicht gegen den Vierten spielt, so kann man den Zweiten nicht vom Dritten unterscheiden.

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

Wir betrachten die Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto a*b,$

die einem Paar ${}(a,b)$ diejenige Zahl zuordnet, die entsteht, wenn man im Zehnersystem die Zahl ${}b$ ${}a$-fach hintereinander schreibt.

1. Bestimme ${}7*6$.
2. Bestimme ${}4*13$.
3. Ist die Verknüpfung kommutativ?
4. Ist die Verknüpfung assoziativ?
5. Besitzt die Verknüpfung ein neutrales Element?

Lösung

1. Es ist

   ${}7*6=6666666\,.$

2. Es ist

   ${}4*13=13131313\,.$

3. Die Verknüpfung ist nicht kommutativ, es ist  ${}2*1=11$,  aber  ${}1*2=2$. 
4. Die Verknüpfung ist nicht assoziativ, es ist  ${}2*(2*2)=2*(22)=2222$,  aber  ${}(2*2)*2=22*2$  besteht aus ${}22$ Zweien.
5. Die Verknüpfung besitzt kein neutrales Element. Von links ist zwar  ${}1*b=b$,  daher ist ${}1$ der einzige Kandidat, von rechts ist aber im Allgemeinen (beispielsweise für ${}b=2$)

   ${}b*1\neq b\,.$

Aufgabe (3 (1+2) Punkte)

Es sei ${}{\left(G,\cdot ,1\right)}$ eine Gruppe. Es seien  ${}a,b,c\in G$  Elemente mit

${}a\cdot b\cdot c=1\,.$

1. Zeige, dass das Inverse von ${}b$ gleich ${}c\cdot a$ ist.
2. Zeige, dass das Inverse von ${}b$ im Allgemeinen nicht gleich ${}a\cdot c$ ist.

Lösung

1. Wegen

   ${}a\cdot b\cdot c=1\,$

   sind ${}a$ und ${}b\cdot c$ invers zueinander, daher ist auch

   ${}b\cdot c\cdot a=1\,,$

   also ist ${}c\cdot a$ das Inverse von ${}b$.

2. Es seien ${}a,b$ zwei Elemente einer Gruppe mit  ${}a\cdot b\neq b\cdot a$  und sei

   ${}c:=b^{-1}\cdot a^{-1}\,,$

   so dass also

   ${}a\cdot b\cdot c=1\,$

   ist. Es ist dann

   ${}b\cdot a\cdot c=b\cdot a\cdot b^{-1}\cdot a^{-1}\neq 1\,,$

   da aus

   ${}b\cdot a\cdot b^{-1}\cdot a^{-1}=1\,$

   durch Multiplikation mit ${}a$ von rechts und dann mit ${}b$ von rechts

   ${}b\cdot a=a\cdot b\,$

   gelten müsste.

Aufgabe (2 Punkte)

Beweise, dass der Polynomring ${}K[X]$ über einem Körper ${}K$ selbst kein Körper ist.

Lösung

In einem Körper besitzt jedes Element ${}\neq 0$ ein multiplikatives Inverses. Dies ist beim Polynomring nicht der Fall, beispielsweise besitzt die Variable ${}X$ kein Inverses, da das Produkt von ${}X$ mit jedem Polynom  ${}P\neq 0$  einen Grad ${}\geq 1$ besitzt.

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

Wir betrachten die Relation im nebenstehenden Diagramm, wobei eine Pfeil ${}x\rightarrow y$ bedeutet, dass ${}x$ von ${}y$ gefressen wird.

1. Was frisst ein Polarbear?
2. Von wem wird ein Capelin gefressen?
3. Welche Tiere stehen an der Spitze der Nahrungskette?
4. Ist die Relation transitiv?
5. Ist die Relation antisymmetrisch?

Lösung

1. Ein Polarbear frisst Arctic cod, Ringed seal und Harbour seal.
2. Capelin wird von Harbour seal und Harp seal gefressen.
3. Polar bear, Killer whale und Arctic birds stehen an der Spitze der Nahrungskette, da von ihnen kein Pfeil ausgeht.
4. Die Relation ist nicht transitiv, da beispielsweise ein Pfeil von Arctic cod nach Ringed seal und ein Pfeil von Ringed seal nach Killer whale geht, aber kein direkter Pfeil von Arctic cod nach Killer whale.
5. Die Relation ist antisymmetrisch, da die Voraussetzung, dass zwei Objekte durch Pfeil und gegenläufigen Pfeil verbunden sind, überhaupt nicht vorkommt, und damit die in der Antisymmetrie geforderte Implikation automatisch erfüllt ist, da der Vordersatz stets falsch ist.

Aufgabe (3 Punkte)

Zeige, dass für natürliche Zahlen die folgenden Teilbarkeitsbeziehungen gelten.

1. Für jede natürliche Zahl ${}a$ gilt ${}1\,{|}\,a$ und ${}a\,{|}\,a$.
2. Für jede natürliche Zahl ${}a$ gilt ${}a\,{|}\,0$.
3. Gilt ${}a\,{|}\,b$ und ${}b\,{|}\,c$, so gilt auch ${}a\,{|}\,c$.
4. Gilt ${}a\,{|}\,b$ und ${}c\,{|}\,d$, so gilt auch ${}ac\,{|}\,bd$.
5. Gilt ${}a\,{|}\,b$, so gilt auch ${}ac\,{|}\,bc$ für jede natürliche Zahl ${}c$.
6. Gilt ${}a\,{|}\,b$ und ${}a\,{|}\,c$, so gilt auch ${}a\,{|}\,{\left(rb+sc\right)}$ für beliebige natürliche Zahlen ${}r,s$.

Lösung

1. Ist klar wegen

   ${}a=a\cdot 1\,.$

2. Ist klar wegen

   ${}0=a\cdot 0\,.$

3. Die beiden Voraussetzungen bedeuten die Existenz von  ${}s,t\in \mathbb {N}$  mit  ${}b=as$  und  ${}c=bt$.  Somit ist

   ${}c=bt=(as)t=a(st)\,$

   und ${}a$ ist auch ein Teiler von ${}c$.

4. Aus den Voraussetzungen  ${}b=as$  und  ${}d=tc$  ergibt sich direkt

   ${}bd=astc=acts\,,$

   also ist ${}ac$ ein Teiler von ${}bd$.

5. Aus der Voraussetzung  ${}b=as$  ergibt sich direkt

   ${}bc=acs\,,$

   also ist ${}ac$ ein Teiler von ${}bc$.

6. Aus den Voraussetzungen  ${}b=at$  und  ${}c=au$  ergibt sich direkt mit dem Distributivgesetz

   ${}rb+sc=rat+sau=a(rt+su)\,,$

   also ist ${}a$ ein Teiler von ${}rb+sc$.

Aufgabe (3 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}1085$ und ${}806$ und schreibe die beiden Zahlen als Vielfache des größten gemeinsamen Teilers.

Lösung

Es ist

${}1085=1\cdot 806+279\,,$

${}806=2\cdot 279+248\,,$

${}279=1\cdot 248+31\,,$

${}248=8\cdot 31\,.$

Der größte gemeinsame Teiler ist also ${}31$. Aus den Rechnungen erhält man

${}806=2\cdot 279+248=2(248+31)+248=3\cdot 248+2\cdot 31=3\cdot 8\cdot 31+2\cdot 31=26\cdot 31\,$

und

${}1085=806+279=26\cdot 31+9\cdot 31=35\cdot 31\,.$

Aufgabe (8 (3+2+3) Punkte)

Wir betrachten auf der Menge ${}C$ aller stetigen Funktionen von ${}\mathbb {R}$ nach ${}\mathbb {R}$ die folgende Relation: Es ist ${}f\sim g$, falls es eine nullstellenfreie stetige Funktion ${}\alpha \colon \mathbb {R} \rightarrow \mathbb {R}$ mit

${}f=g\cdot \alpha \,$

gibt.

1. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.
2. Zeige, dass aus ${}f\sim g$ folgt, dass die Nullstellenmenge von ${}f$ und von ${}g$ übereinstimmen.
3. Zeige, dass die beiden Funktionen

   ${}f(x)=x\,$

   und

   ${}g(x)=x^{2}\,$

   nicht zueinander äquivalent sind.

Lösung

1. Es ist ${}f\sim f$, da

   ${}f=1\cdot f\,$

   ist, man also für ${}\alpha$ die konstante Funktion mit dem Wert ${}1$ nehmen kann, die stetig ist und keine Nullstelle besitzt. Zum Nachweis der Symmetrie sei

   ${}f=g\cdot \alpha \,$

   mit einer stetigen nullstellenfreien Funktion ${}\alpha$. Dann ist auch die Funktion

   ${\frac {1}{\alpha }}\colon \mathbb {R} \longrightarrow \mathbb {R} ,\,x\longmapsto {\frac {1}{\alpha (x)}},$

   wohldefiniert, nullstellenfrei und nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2020-2021)) auch stetig. Damit gilt

   ${}f\cdot {\frac {1}{\alpha }}=g\,.$

   Zum Nachweis der Transitivität gelte

   ${}f=g\cdot \alpha \,$

   und

   ${}g=h\cdot \beta \,$

   mit stetigen nullstellenfreien Funktionen ${}\alpha ,\beta$. Dann ist

   ${}f=g\cdot \alpha =h\cdot \beta \cdot \alpha \,$

   und ${}\beta \cdot \alpha$ ist ebenfalls nach Lemma 10.6 (Mathematik für Anwender (Osnabrück 2020-2021)) eine stetige nullstellenfreie Funktion.

2. Es sei

   ${}f=g\cdot \alpha \,$

   mit ${}\alpha$ stetig und nullstellenfrei. Dann ist für jedes ${}x\in \mathbb {R}$

   ${}f(x)=g(x)\cdot \alpha (x)\,.$

   Wegen

   ${}\alpha (x)\neq 0\,$

   gilt

   ${}f(x)=0\,$

   genau dann, wenn

   ${}g(x)=0\,$

   ist. Dies bedeutet, dass ${}f$ und ${}g$ die gleichen Nullstellen besitzen.

3. Nehmen wir an, dass ${}x$ und ${}x^{2}$ im beschriebenen Sinne äquivalent sind. Dann gibt es eine stetige nullstellenfreie Funktion ${}\alpha$ mit

   ${}x^{2}=\alpha (x)\cdot x\,$

   für alle ${}x\in \mathbb {R}$. Für  ${}x\neq 0$  bedeutet dies

   ${}\alpha (x)={\frac {x^{2}}{x}}=x\,.$

   Wegen der vorausgesetzten Stetigkeit von ${}\alpha$ bedeutet dies nach Lemma 51.7 (Grundkurs Mathematik (Osnabrück 2022-2023))  (2), dass auch

   ${}\alpha (0)=0\,$

   sein muss. Dies widerspricht aber der vorausgesetzten Nullstellenfreiheit von ${}\alpha$.

Aufgabe (6 (4+2) Punkte)

1. Finde den kleinsten Exponenten  ${}n\geq 2$  derart, dass die Potenzierung

   $\mathbb {Z} /(10)\longrightarrow \mathbb {Z} /(10),\,x\longmapsto x^{n},$

   die Identität ist.

2. Was bedeutet dies für die Endziffer im Zehnersystem beim Potenzieren von natürlichen Zahlen?

Lösung

1. Wir gehen die Exponenten

   ${}n=2,3,4,...\,$

   durch und schauen, ob die Abbildung

   $\mathbb {Z} /(10)\longrightarrow \mathbb {Z} /(10),\,x\longmapsto x^{n},$

   die Identität ist oder nicht. Alle Rechnungen werden in ${}\mathbb {Z} /(10)$ durchgeführt.

   ${}n=2\,.$

   Wegen

   ${}2^{2}=4\neq 2\,$

   ist dies nicht die Identität.

   ${}n=3\,.$

   Wegen

   ${}2^{3}=8\neq 2\,$

   ist dies nicht die Identität.

   ${}n=4\,.$

   Wegen

   ${}2^{4}=16=6\neq 2\,$

   ist dies nicht die Identität.

   ${}n=5\,.$

   Es ist

   ${}2^{5}=32=2\,,$

   ${}3^{5}=243=3\,,$

   ${}4^{5}={\left(2^{5}\right)}^{2}=2^{2}=4\,,$

   ${}5^{5}=5\,.$

   Für ${}x$ zwischen ${}6$ und ${}9$ gehört ${}-x$ zum bereits untersuchten Bereich und es ist

   ${}(-x)^{5}=(-1)^{5}x^{5}=-x\,.$

   Daher ist die fünfte Potenzierung die Identität. Der minimale Exponent ist somit ${}5$.

2. Die Endziffer im Zehnersystem ist einfach der Rest modulo ${}10$. Daher bedeutet das Ergebnis, dass die Endziffer der fünften Potenz einer natürlichen Zahl stets mit deren Endziffer übereinstimmt, und dass dies nicht für die zweite, dritte oder vierte Potenz gilt.

Aufgabe (4 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen. Zeige, dass eine Äquivalenzrelation ${}\sim _{1}$ auf ${}M$ genau dann konjugiert-isomorph zu einer Äquivalenzrelation ${}\sim _{2}$ auf ${}N$ ist, wenn beide Äquivalenzrelationen das gleiche Klassenanzahltupel besitzen.

Lösung

Es sei ${}\varphi \colon M\rightarrow N$ eine bijektive Abbildung, die eine Isomorphie zwischen und ${}\sim _{1}$ und ${}\sim _{2}$ induziert. Dann werden unter ${}\varphi$ direkt Äquivalenzklassen zu ${}\sim _{1}$ auf Äquivalenzklassen zu ${}\sim _{2}$ abgebildet und daher stimmen die Klassenanzahltupel überein.

Wenn umgekehrt die beiden Klassenanzahltupel übereinstimmen, so erhält man zunächst eine Bijektion zwischen den beiden Quotientenmengen derart, dass die Anzahlen in den jeweiligen Äquivalenzklassen gleich sind. Auf jeder Äquivalenzklasse zu ${}\sim _{1}$ kann man eine bijektie Abbildung in die entsprechende Äquivalenzklasse zu ${}\sim _{2}$ definieren. Diese setzen sich zu einer bijektiven Abbildung ${}\varphi \colon M\rightarrow N$ zusammen, die die Äquivalenzklassen in Äquivalenzklassen überführen und daher eine Isomorphie der Äquivalenzrelationen bewirken.

Aufgabe (3 Punkte)

Man erläutere die wesentlichen Konzepte und Objekte in Satz 17.13 (Diskrete Mathematik (Osnabrück 2026)) für den Fall  ${}d=1$. 

Lösung

Es sei  ${}a_{d}=a\neq 0$.  Die Rekursionsbedingung aus Teil (1) ist

${}x_{n}=ax_{n-1}\,.$

Ein Anfangsglied ${}x_{0}$ legt direkt die Folge  ${}x_{n}=a^{n}x_{0}$  fest. Die relevanten Polynome aus Teil (2) sind

${}Q(t)=1-at\,$

und (das konstante Polynom)

${}P(t)=x_{0}\,.$

Es ist ja

${}{\frac {x_{0}}{1-at}}=x_{0}\sum _{n=0}^{\infty }a^{n}t^{n}\,$

gemäß Beispiel 17.8 (Diskrete Mathematik (Osnabrück 2026)). In (3) liegt das Polynom ${}t-a$ unmittelbar faktorisiert vor, es ist also  ${}\lambda =a$  die einzige Nullstelle (mit Vielfachheit ${}1$). Hier ist wieder ${}P$ konstant und

${}x_{n}=a^{n}P\,.$

Aufgabe (2 Punkte)

Es sei ${}{\mathcal {M}}$ ein Matroid auf einer Menge ${}E$ und  ${}B_{1},B_{2}\in {\mathcal {M}}$  Basen. Zeige

${}{\#\left(B_{1}\right)}={\#\left(B_{2}\right)}\,.$

Lösung

Angenommen, es wäre  ${}{\#\left(B_{1}\right)}\neq {\#\left(B_{2}\right)}$,  ohne Einschränkung sei  ${}{\#\left(B_{1}\right)}+1\leq {\#\left(B_{2}\right)}$.  Dann existiert nach der Austauscheigenschaft ein  ${}a\in B_{2}\setminus B_{1}$  mit  ${}B_{1}\cup \{a\}\in {\mathcal {M}}$,  was der Maximalität von ${}B_{1}$ widerspricht.

Aufgabe (7 (3+2+2) Punkte)

1. Bestimme die linearen Rekursionen mit der Eigenschaft, dass ihre zugehörige Matrix gleich der Adjazenzmatrix eines Graphen ist. Wie sieht in diesen Fällen die Matrix, wie der Graph, wie die lineare Rekursion aus?
2. Bestimme das charakteristische Polynom, die Eigenwerte und die Eigenvektoren in diesen Fällen.
3. Wie sieht die Lösung der linearen Rekursion zu einem beliebigen Startwerttupel in diesen Fällen aus?

Lösung

1. Eine lineare Rekursion besitzt die Form

   ${}x_{n}=a_{1}x_{n-1}+a_{2}x_{n-2}+\cdots +a_{d}x_{n-d}\,$

   mit  ${}a_{d}\neq 0$,  die zugehörige Matrix ist

   ${\begin{pmatrix}a_{1}&a_{2}&\ldots &a_{d}\\1&0&\ldots &0\\\vdots &\ddots &\ddots &\vdots \\0&\ldots &1&0\end{pmatrix}}.$

   Die Adjazenzmatrix eines Graphen ist symmetrisch und in der Diagonalen stehen nur Nullen. Dies gilt für die Matrix zu einer linearen Rekursion genau dann, wenn  ${}d=2$,   ${}a_{1}=0$  und  ${}a_{2}=1$  ist. Das ist der lineare Graph der Länge ${}2$ mit der Matrix

   ${\begin{pmatrix}0&1\\1&0\end{pmatrix}}.$

   Die lineare Rekursion ist dann

   ${}x_{n}=x_{n-2}\,.$

2. Das charakteristische Polynom ist

   ${}\det {\begin{pmatrix}t&-1\\-1&t\end{pmatrix}}=t^{2}-1=(t-1)(t+1)\,,$

   die Eigenwerte sind ${}1$ und ${}-1$. Ein Eigenvektor zum Eigenwert ${}1$ ist ${}{\begin{pmatrix}1\\1\end{pmatrix}}$, ein Eigenvektor zum Eigenwert ${}-1$ ist ${}{\begin{pmatrix}1\\-1\end{pmatrix}}$.

3. Der Startvektor sei

   ${\begin{pmatrix}x_{1}\\x_{0}\end{pmatrix}}.$

   Es ist

   ${}{\begin{pmatrix}x_{1}\\x_{0}\end{pmatrix}}={\frac {x_{1}+x_{0}}{2}}{\begin{pmatrix}1\\1\end{pmatrix}}+{\frac {x_{1}-x_{0}}{2}}{\begin{pmatrix}1\\-1\end{pmatrix}}\,$

   die Beschreibung dieses Vektors als Linearkombination mit den Eigenvektoren. Nach Satz 16.6 (Diskrete Mathematik (Osnabrück 2026)) ist

   ${}{\begin{pmatrix}x_{n+1}\\x_{n}\end{pmatrix}}={\frac {x_{1}+x_{0}}{2}}{\begin{pmatrix}1\\1\end{pmatrix}}+(-1)^{n}{\frac {x_{1}-x_{0}}{2}}{\begin{pmatrix}1\\-1\end{pmatrix}}\,,$

   die Lösungsfolge ist also abwechselnd

   $x_{0},x_{1},x_{0},x_{1},x_{0},x_{1},\ldots .$

   Dieses Ergebnis ist auch vom Graphen her klar.

Aufgabe (6 Punkte)

Beweise den Satz über nichtgeschlossene Eulerzüge.

Lösung

Ein nicht geschlossener Eulerzug besitzt einen Anfangspunkt ${}u$ und einen davon verschiedenen Endpunkt ${}v$. Wenn man den Eulerzug durchläuft und dabei für jeden Punkt die Grade zählt, so erhöht sich bei jedem Durchlauf durch einen Punkt (egal ob ${}u$ oder ${}v$ oder sonst ein Punkt) der Grad um ${}2$. Am Anfang und am Ende kommt für ${}u$ bzw. ${}v$ nochmal ${}1$ dazu.

Es seien ${}u$ und ${}v$ die beiden Punkte mit ungeradem Grad. Wenn ${}\{u,v\}$ nicht zu ${}E$ gehört, so nimmt man diese Kante hinzu und erhält einen neuen Graphen ${}G'$, bei dem nun alle Knotenpunkte einen geraden Grad besitzen. Nach Satz 25.7 (Diskrete Mathematik (Osnabrück 2026)) gibt es in ${}G'$ einen geschlossenen Eulerzug. Dieser ist ohne die Kante ${}\{u,v\}$ ein nichtgeschlossener Eulerzug von ${}G$. Wenn hingegen ${}\{u,v\}$ zu ${}E$ gehört, so nimmt man einen neuen Punkt ${}w$ zur Knotenmenge und die Kanten ${}\{u,w\}$ und ${}\{v,w\}$ zur Kantenmenge hinzu. Im neuen Graphen ${}G'$ besitzt wieder jeder Knoten einen geraden Grad. Ein geschlossener Eulerzug von ${}G'$ enthält den Kantenzug ${}\{u,w\},\{w,v\}$. Da ${}w$ in sonst keiner Kante auftritt, erhält man, indem man dieses Teilstück und ${}w$ weglässt, einen nichtgeschlossenen Eulerzug von ${}G$.