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

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine antimonotone Abbildung

   $F:M_1⟶M_2,$

   zwischen den geordneten Mengen $(M_1,{\le }_1)$ und $(M_2,{\le }_2)$.

2. Der Multinomialkoeffizient

   $(\genfrac{}{}{0ex}{}{n}{r_1,\dots ,r_k})$

   $n$ über $r_1,\dots ,r_k$.

3. Linksisomorphe Abbildungen $f_1:L_1\to M$ und $f_2:L_2\to M$ zu Mengen $L_1,L_2,M$.
4. Der Grad eines Punktes  $v\in V$  in einem Graphen  $G=(V,E)$. 
5. Ein zusammenhängender Graph $(V,E)$.
6. Die Eigenschaft einer Paarung $P$ in einem Graphen  $G=(V,E)$,  einen Knotenpunkt  $v\in V$  abzudecken.

Lösung

1. Die Abbildung

   $F:M_1⟶M_2,$

   heißt antimonoton, wenn für alle  $x,x^{\prime }\in M_1$  mit  $x{\le }_1{x}^{\prime }$  stets  $F(x){\ge }_{2}F(x^{\prime })$  gilt.

2. Der Multinomialkoeffizient ist

   $(\genfrac{}{}{0ex}{}{n}{r_1,\dots ,r_k}):=\frac{n!}{r_1!\cdots r_k!}.$

3. Die Abbildungen $f_1$ und $f_2$ heißen linksisomorph, wenn es eine bijektive Abbildung $\phi :L_1\to L_2$ mit

   $f_1=f_2\circ \phi$

   gibt.

4. Der Grad eines Punktes in einem ungerichteten Graphen ist die Anzahl seiner Nachbarn.
5. Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten  $u,v\in V$  einen Weg gibt, der $u$ und $v$ verbindet.
6. Die Paarung $P$ deckt $v$ ab, wenn es eine Kante aus $P$ gibt, zu der $v$ gehört.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Äquivalenzrelation zu einer Untergruppe  $H\subseteq G$  in einer kommutativen Gruppe $G$.
2. Der Satz über die Charakterisierung von isomorphen Abbildungen zwischen endlichen Mengen.
3. Der Paarungssatz (Heiratssatz)

Lösung

1. Es sei $(G,0,+)$ eine kommutative Gruppe,  $H\subseteq G$  eine Untergruppe und ${\sim }_H$ die durch $H$ auf $G$ definierte Relation. Dann liegt eine Äquivalenzrelation vor, und die Äquivalenzklasse zu $0$ ist gerade $H$.
2. Es seien $f_1:L_1\to M_1$ und $f_2:L_2\to M_2$ Abbildungen zwischen endlichen Mengen. Dann sind $f_1$ und $f_2$ genau dann zueinander isomorph, wenn ihre Faseranzahltupel übereinstimmen.
3. Es sei $M$ eine Menge, es sei $I$ eine endliche Indexmenge und zu jedem  $i\in I$  sei eine Teilmenge  $M_i\subseteq M$  gegeben. Zu einer Teilmenge  $J\subseteq I$  setzen wir

   $M_J=\bigcup _{j\in J}{M}_j.$

   Für jede Teilmenge  $J\subseteq I$  gelte

   $\mathrm{\#}\left(M_J\right)\ge \mathrm{\#}\left(J\right).$

   Dann gibt es eine injektive Abbildung

   $f:I⟶M$

   mit

    $f(i)\in M_i$. 

Aufgabe (3 Punkte)

Es seien $A,B,C$ Mengen. Zeige, dass die folgenden Aussagen zueinander äquivalent sind.

1.  $A\subseteq B\cup C$. 
2.  $A\setminus B\subseteq C$. 
3.  $A\setminus C\subseteq B$. 

Lösung

Von (1) nach (2). Es gelte also  $A\subseteq B\cup C$  und es ist  $A\setminus B\subseteq C$  zu zeigen. Es sei also  $x\in A\setminus B$.  Das bedeutet  $x\in A$  und  $x\notin B$.  Nach Voraussetzung (1) gilt wegen  $x\in A$  auch  $x\in B\cup C$  und wegen  $x\notin B$  gilt  $x\in C$. 

Von (2) nach (1). Es gelte also  $A\setminus B\subseteq C$  und es ist  $A\subseteq B\cup C$  zu zeigen. Es sei also  $x\in A$.  Wir machen eine Fallunterscheidung. Bei  $x\in B$  ist auch  $x\in B\cup C$.  Bei  $x\notin B$  gilt wegen  $x\in A$  zunächst  $x\in A\setminus B$  und daher wegen der Voraussetzung  $A\setminus B\subseteq C$  auch  $x\in C$,  also wieder  $x\in B\cup C$. 

Die Äquivalenz von (1) und (3) ergibt sich genauso mit vertauschten Rollen von $B$ und $C$.

Aufgabe (4 Punkte)

Hanny, Nanny, Fanny und Sanny leben auf dem Ponyhof. Heute machen sie einen Ausflug mit den Ponies Pona, Pone, Pono und Ponu. Jedes der Mädchen sitzt dabei genau auf einem Pony, und sie reiten hintereinander. Folgende Fakten sind bekannt.

1. Fanny sitzt nicht auf Pona.
2. Pone und Ponu vertragen sich nicht so gut und laufen daher nicht direkt hintereinander.
3. Nanny sitzt auf Pone oder auf Pono.
4. Sanny reitet auf Pona oder auf Pone.
5. Nanny reitet direkt hinter Sanny.
6. Auf Ponu sitzt nicht Sanny.
7. Pona läuft direkt zwischen Pone und Pono.
8. Auf Pono sitzt weder Fanny noch Hanny.
9. Sanny reitet weiter vorne als Hanny.

Wer sitzt auf welchem Pony und in welcher Reihenfolge laufen sie?

Lösung

Nach (7) liegt der Ponyabschnitt Pone-Pona-Pono oder Pono-Pona-Pone vor. Nach (2) sind somit nur die Ponyreihenfolgen Pone-Pona-Pono-Ponu oder Ponu-Pono-Pona-Pone möglich. Nach (8) sitzt auf Pono Nanny oder Sanny, nach (4) sitzt aber Sanny auf Pona oder Pone. Deshalb sitzt Nanny auf Pono. Nach (5) reitet Nanny direkt hinter Sanny. Bei der Reihenfolge Ponu-Pono-Pona-Pone müsste also Sanny auf Ponu reiten, was nach (4) ausgeschlossen ist. Also ist die Reihenfolge Pone-Pona-Pono-Ponu und Sanny reitet auf Pona. Nach (9) reitet Hanny auf Ponu und folglich reitet Fanny auf Pone.

Reihenfolge	Pony	Reiterin
1	Pone	Fanny
2	Pona	Sanny
3	Pono	Nanny
4	Ponu	Hanny

Aufgabe (3 Punkte)

Es soll Holz unterschiedlicher Länge (ohne Abfall) in Stücke zerlegt werden, die zwischen $30$ und $40$ cm lang sein sollen (jeweils einschließlich). Für welche Holzlängen ist dies möglich?

Lösung

Es sei $\ell$ die Länge des Holzes, das zerlegt werden soll. Für $\ell <30$ ist eine Zerlegung offenbar nicht möglich. Für  $30\le \ell \le 40$  kann man das Stück so lassen, wie es ist, eine Zerlegung ist also möglich. Für  $40<\ell <60$  ist eine Zerlegung nicht möglich, da das Stück zu lang ist, um es direkt zu übernehmen, aber zu kurz, um es in zwei oder mehr Teile zu zerlegen. Für  $60\le \ell \le 80$  kann man das Stück in zwei (beispielsweise gleichgroße) Teile unterteilen, eine Zerlegung ist also möglich. Für  $80<\ell <90$  ist keine Zerlegung möglich. Für zwei Teile ist das Stück nämlich zu lang und für drei oder mehr Teile ist es zu kurz. Ab

$\ell \ge 90$

ist eine Zerlegung stets möglich. Die Länge erfüllt dann nämlich

$30s\le \ell <30(s+1)$

mit einer natürlichen Zahl  $s\ge 3$.  Wenn man $\ell$ durch $s$ dividiert, erhält man

$30\le \frac{\ell }{s}<\frac{30(s+1)}{s}=30\frac{(s+1)}{s}\le 30\frac{4}{3}\le 40,$

was als Länge eines Teilstücks erlaubt ist.

Aufgabe (3 Punkte)

Zeige, dass die Binomialkoeffizienten die rekursive Beziehung

$(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1})$

erfüllen.

Lösung

Es ist

$\begin{array}{cc}(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1})& =\frac{n!}{(n-k)!k!}+\frac{n!}{(n-(k-1))!(k-1)!}\\ & =\frac{n!}{(n-k)!k!}+\frac{n!}{(n+1-k)!(k-1)!}\\ & =\frac{(n+1-k)\cdot n!}{(n+1-k)!k!}+\frac{k\cdot n!}{(n+1-k)!k!}\\ & =\frac{(n+1-k+k)\cdot n!}{(n+1-k)!k!}\\ & =\frac{(n+1)!}{(n+1-k)!k!}\\ & =(\genfrac{}{}{0ex}{}{n+1}{k}).\end{array}$

Aufgabe (3 Punkte)

Erstelle eine Liste von sämtlichen Permutationen auf der Menge $\{A,B,C,D\}$ und bestimme, welche von ihnen fixpunktfrei sind.

Lösung

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$B$	$C$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$B$	$D$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$C$	$B$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$C$	$D$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$D$	$B$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$A$	$D$	$C$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$A$	$C$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$A$	$D$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$C$	$A$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$C$	$D$	$A$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$D$	$A$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$B$	$D$	$C$	$A$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$A$	$B$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$A$	$D$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$B$	$A$	$D$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$B$	$D$	$A$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$D$	$A$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$C$	$D$	$B$	$A$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$A$	$B$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$A$	$C$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$B$	$A$	$C$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$B$	$C$	$A$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$C$	$A$	$B$

$P$	$A$	$B$	$C$	$D$
$Z(P)$	$D$	$C$	$B$	$A$

Eine Durchsicht der Liste zeigt, dass es $9$ fixpunktfreie Permutationen gibt.

Aufgabe (2 Punkte)

Beweise den Satz über die Lösbarkeit von Gleichungen in einer Gruppe $G$.

Lösung

Wir betrachten die linke Gleichung. Aus beidseitiger Multiplikation mit $a^{-1}$ von links folgt, dass nur

$x=a^{-1}\circ b$

als Lösung in Frage kommt. Wenn man dies einsetzt, so sieht man, dass es sich in der Tat um eine Lösung handelt.

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

Welche der folgenden Abbildungen sind Gruppenhomomorphismen?

1. $({ℝ}_{+},1,\cdot )⟶({ℝ}_{+},1,\cdot ),x⟼\sqrt{x}.$

2. $(ℝ,0,+)⟶(ℝ,0,+),x⟼\sqrt{x}.$

3. $({ℝ}_{\ge 0},1,\cdot )⟶({ℝ}_{\ge 0},1,\cdot ),x⟼\sqrt{x}.$

4. $({ℝ}_{+},1,\cdot )⟶(ℝ,0,+),x⟼\sqrt{x}.$

Lösung

1. Dies ist ein Gruppenhomomorphismus. Die positiven reellen Zahlen $({ℝ}_{+},1,\cdot )$ bilden mit der Multiplikation eine Gruppe und es gilt

   $\sqrt{xy}=\sqrt{x}\cdot \sqrt{y},$

   da die Quadrate davon übereinstimmen.

2. Dies ist kein Gruppenhomomorphismus, allein schon deshalb, weil die Wurzel für negative Zahlen gar nicht definiert ist.
3. Dies ist kein Gruppenhomomorphismus, da $({ℝ}_{\ge 0},1,\cdot )$ keine Gruppe ist, da $0$ kein inverses Element besitzt.
4. Dies ist kein Gruppenhomomorphismus, da das neutrale Element links nicht auf das neutrale Element rechts abgebildet wird.

Aufgabe (5 Punkte)

Zeige, dass der Polynomring $R[X]$ über einem kommutativen Ring $R$ wieder ein kommutativer Ring ist.

Lösung

Lediglich die Gültigkeit des Assoziativgesetzes für die Multiplikation und des Distributivgesetzes sind nicht unmittelbar klar. Zum Nachweis dieser Eigenschaften schreiben wir abkürzend die beteiligten Polynome als

$\sum _i{a}_i{X}^i,\sum _j{b}_j{X}^j\text{ und }\sum _k{c}_k{X}^k.$

Mit diesen Bezeichnungen ist

$\begin{array}{cc}\left(\left(\sum _i{a}_i{X}^i\right)\left(\sum _j{b}_j{X}^j\right)\right)\left(\sum _k{c}_k{X}^k\right)& =\left(\sum _r\left(\sum _{i+j=r}{a}_i{b}_j\right)X^r\right)\left(\sum _k{c}_k{X}^k\right)\\ & =\left(\sum _s\left(\sum _{i+j+k=s}{a}_i{b}_j{c}_k\right)X^s\right),\end{array}$

woraus wegen der Symmetrie des Ausdrucks die Assoziativität ablesbar ist. Ferner ist

$\begin{array}{cc}\left(\sum _i{a}_i{X}^i\right)(\left(\sum _j{b}_j{X}^j\right)+\left(\sum _j{c}_j{X}^j\right))& =\left(\sum _i{a}_i{X}^i\right)\left(\sum _j(b_j+c_j)X^j\right)\\ & =\sum _r\left(\sum _{i+j=r}{a}_i(b_j+c_j)\right)X^r\\ & =\sum _r(\sum _{i+j=r}{a}_i{b}_j+a_i{c}_j)X^r\\ & =\sum _r\left(\sum _{i+j=r}{a}_i{b}_j\right)X^r+\sum _r\left(\sum _{i+j=r}{a}_i{c}_j\right)X^r\\ & =\left(\sum _i{a}_i{X}^i\right)\left(\sum _j{b}_j{X}^j\right)+\left(\sum _i{a}_i{X}^i\right)\left(\sum _j{c}_j{X}^j\right),\end{array}$

was die Distributivität bedeutet.

Aufgabe (4 Punkte)

Zeige, dass für jede ungerade Zahl $n$ die Zahl $25n^2-17$ ein Vielfaches von $8$ ist.

Lösung

Eine ungerade Zahl $n$ besitzt die Form $n=2k+1$ mit einer ganzen Zahl $k$. Somit ist

$\begin{array}{cc}25n^2-17& =25(2k+1{)}^2-17\\ & =25(4k^2+4k+1)-17\\ & =25\cdot 4\cdot k(k+1)+25-17\\ & =25\cdot 4\cdot k(k+1)+8.\end{array}$

Die $8$ hinten ist ein Vielfaches von $8$. Genau eine der beiden Zahlen $k$ und $k+1$ ist gerade, also von der Form $2m$. Daher ist $4\cdot k(k+1)$ ein Vielfaches von $8$ und somit ist die gesamte Zahl ein Vielfaches von $8$.

Aufgabe (3 Punkte)

Bestimme in $\mathbb{Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von $71894$ und $45327$.

Lösung

Der Euklidische Algorithmus liefert:

$71894=1\cdot 45327+26567$

$45327=1\cdot 26567+18760$

$26567=1\cdot 18760+7807$

$18760=2\cdot 7807+3146$

$7807=2\cdot 3146+1515$

$3146=2\cdot 1515+116$

$1515=13\cdot 116+7$

$116=16\cdot 7+4$

$7=1\cdot 4+3$

$4=1\cdot 3+1.$

Die Zahlen $71894$ und $45327$ sind also teilerfremd.

Aufgabe (4 Punkte)

Es sei  $n\in \mathbb{N}$  und $\mathbb{Z}/(n)$ der zugehörige Restklassenring. Zeige, dass  $a\in \mathbb{Z}$  genau dann eine Einheit modulo $n$ ist, wenn $a$ und $n$ teilerfremd sind.

Lösung

Sind $a$ und $n$ teilerfremd, so gibt es nach Satz 8.2 (Diskrete Mathematik (Osnabrück 2026)) eine Darstellung der $1$, es gibt also ganze Zahlen $r,s$ mit

$ra+sn=1.$

Betrachtet man diese Gleichung modulo $n$, so ergibt sich  $ra=1$  in $\mathbb{Z}/(n)$. Damit ist $a$ eine Einheit mit dem inversen Element  $a^{-1}=r$. 

Ist umgekehrt $a$ eine Einheit in $\mathbb{Z}/(n)$, so gibt es ein  $r\in \mathbb{Z}/(n)$  mit  $ar=1$  in $\mathbb{Z}/(n)$. Das bedeutet aber, dass $ar-1$ ein Vielfaches von $n$ ist, sodass also

$ar-1=sn$

gilt. Dann ist aber wieder  $ar-sn=1$  und $a$ und $n$ sind teilerfremd.

Aufgabe (3 Punkte)

Es sei $R$ ein endlicher kommutativer Ring mit $n$ Elementen,  $R\ne 0$.  Zeige, dass die Addition $+:R\times R\to R$ und die Multiplikation $\cdot :R\times R\to R$ nicht zueinander isomorph sind.

Lösung

Es ist $(R,+,0)$ eine endliche Gruppe, die Faser zu $y$ unter der Additionsabbildung besteht aus den $n$ Elementen $\{(x,z-x)\mid x\in R\}$. Das Faseranzahltupel der Addition ist also $(n,n,\dots ,n)$. Die Faser der Multiplikationsabbildung umfasst jedenfalls gemäß Lemma 5.11 (Diskrete Mathematik (Osnabrück 2026))  (1) die Elemente $\{(x,0),x\in R\}$ und $\{(0,y),y\in R\}$, also zumindest $2n-1$ Elemente. Da  $n\ge 2$  vorausgesetzt wird, ist  $2n-1>n$  und das Faseranzahltupel der Multiplikation ist vom Faseranzahltupel der Addition verschieden. Nach Satz 15.5 (Diskrete Mathematik (Osnabrück 2026)) können die beiden Verknüpfungen nicht isomorph sein.

Aufgabe (2 Punkte)

Es sei $M$ eine $d\times d$-Matrix über dem Körper $K$ und sei $\left(\begin{array}{c}{c}_1\\ ⋮\\ c_d\end{array}\right)$ ein Eigenvektor von $M$ mit dem Eigenwert $\lambda$. Zeige, dass

$v_n={\lambda }^n\left(\begin{array}{c}{c}_1\\ ⋮\\ c_d\end{array}\right)$

die Lösung der Matrixrekursion

$v_{n+1}=M{v}_n$

zum Startvektor $\left(\begin{array}{c}{c}_1\\ ⋮\\ c_d\end{array}\right)$ ist.

Lösung

Wir beweisen die Aussage durch Induktion über $n$, der Fall  $n=0$  ist direkt die Startsituation. Der Induktionsschritt ergibt sich direkt aus

$\begin{array}{cc}{v}_{n+1}& =M{v}_n\\ & =M\left({\lambda }^n\left(\begin{array}{c}{c}_1\\ ⋮\\ c_k\end{array}\right)\right)\\ & ={\lambda }^{n}M\left(\begin{array}{c}{c}_1\\ ⋮\\ c_k\end{array}\right)\\ & ={\lambda }^n\lambda \left(\begin{array}{c}{c}_1\\ ⋮\\ c_k\end{array}\right)\\ & ={\lambda }^{n+1}\left(\begin{array}{c}{c}_1\\ ⋮\\ c_k\end{array}\right).\end{array}$

Aufgabe (2 Punkte)

Es sei $\phi :G\to H$ ein Graphhomomorphismus. Ist die gleiche Abbildung (auf den Vertexmengen) auch ein Graphhomomorphismus von den Komplementärgraphen $G^c\to H^c$?

Lösung

Dies ist nicht der Fall. Es sei $G$ der zweipunktige kantenfreie Graph und $H$ der zweipunktige lineare Graph. Die Bijektion

$G⟶H$

ist ein Graphhomomorphismus, da es ja links keine Kanten gibt. Bei den Komplementären Graphen vertauschen sich die Rollen. Die einzige Kante in $G^c$ wird dann auf eine Nichtkante in $H^c$ abgebildet, das ist also kein Graphhomomorphismus.

Aufgabe weiter

Wir sind mitten in der WM, das Viertelfinale steht fest und beginnt morgen. Die Zeitung druckt den folgenden Restspielplan (ohne Spiel um Platz 3) ab.

Viertelfinale

$\text{ VF1 }:\underset{\_}{\text{ Arg }}-\underset{\_}{\text{ Deu }}$

$\text{ VF2 }:\underset{\_}{\text{ Usb }}-\underset{\_}{\text{ Bra }}$

$\text{ VF3 }:\underset{\_}{\text{ Eng }}-\underset{\_}{\text{ Kapv }}$

$\text{ VF4 }:\underset{\_}{\text{ Fra }}-\underset{\_}{\text{ Cur }}$

Halbfinale

$\text{ HF1 }:\text{ Sieger VF1 }\underset{\_}{}-\text{ Sieger VF2 }\underset{\_}{}$

$\text{ HF2 }:\text{ Sieger VF3 }\underset{\_}{}-\text{ Sieger VF4 }\underset{\_}{}$

Finale

$\text{ Finale }:\text{ Sieger HF1 }\underset{\_}{}-\text{ Sieger HF2 }\underset{\_}{}$

Wir interpretieren die Begegnungsstriche $-$ als Kanten in einem Graphen $G$.

1. Was ist die Knotenmenge in $G$? Skizziere den Graphen allein mit Punkten und Kanten (ohne jede Bennenung)!
2. Was sind die Zusammenhangskomponenten von $G$? Ist der Graph bipartit?
3. Einige Tage später steht das Finale an. Der Spielplan wurde zwischenzeitlich ergänzt, die unteren Zeilen sehen jetzt so aus (die oberen Zeilen aus dem Viertefinale sind unverändert da).

   $$

   
   

   Halbfinale

   $\text{ HF1 }:\text{ Sieger VF1 }\underset{\_}{\text{ Deu }}-\text{ Sieger VF2 }\underset{\_}{\text{ Usb }}$

   $\text{ HF2 }:\text{ Sieger VF3 }\underset{\_}{\text{ Kapv }}-\text{ Sieger VF4 }\underset{\_}{\text{ Cur }}$

   Finale

   $\text{ Finale }:\text{ Sieger HF1 }\underset{\_}{\text{ Deu }}-\text{ Sieger HF2 }\underset{\_}{\text{ Cur }}$

   Hat sich der Graph $G$ verändert?

4. Es sei nun $\sim$ die Äquivalenzrelation auf $G$, bei der Knotenpunkte zueinander äquivalent sind, wenn sie durch die gleiche Mannschaft besetzt sind. Skizziere den Quotientengraphen  $H=G/\sim$  überschneidungsfrei!
5. Ist der Graph $H$ zusammenhängend? Ist er bipartit?
6. Bestimme die Automorphismengruppe von $H$!

Lösung erstellen

Aufgabe (7 (6+1) Punkte)

Wir betrachten die Ebene, die durch eine Menge von Geraden $G_1,\dots ,G_n$ in Teilgebiete („Länder“) zerschnitten wird. Die Grenze zwischen zwei solchen Gebieten ist also ein Geradenstück.

1. Zeige, dass man die Gebiete mit zwei Farben so färben kann, dass zwei benachbarte Gebiete (die ein echtes Geradenstück gemeinsam haben, ein einzelner gemeinsamer Punkt gilt nicht) eine verschiedene Farbe haben.
2. Skizziere eine solche Färbung in der abgebildeten Situation.

   

Lösung

1. Wir beweisen die Aussage durch Induktion über die Anzahl der Geraden. Bei  $n=1$  gibt es nur eine Gerade und damit zwei Hälften, denen wir unterschiedliche Farben geben. Zum Induktionsschluss setzen wir voraus, dass es zu je $n$ Geraden eine erlaubte Färbung der Gebiete gibt. Es seien $n+1$ Geraden $G_1,\dots ,G_n,G_{n+1}$ gegeben. Es sei eine erlaubte Färbung der Gebiete gegeben, die durch die Geraden $G_1,\dots ,G_n$ festgelegt werden (alte Gebiete), was es nach Induktionsvoraussetzung gibt. Die hinzukommende Gerade

   $H=G_{n+1}$

   verändert natürlich einen Großteil der Gebiete, und zwar zerlegt sie diejenigen Gebiete, die durch $H$ echt zerschnitten werden, in zwei neue Gebiete. Ferner zerlegt $H$ die Gesamtebene in zwei Hälften, die wir $A$ und $B$ nennen. Ein Gebiet zur größeren Geradenkonfiguration liegt somit ganz in $A$ oder in $B$. Wir definieren eine neue Färbung der neuen Gebietsaufteilung durch folgende Vorschrift: Ein (neues) Gebiet, das in $A$ liegt, behält seine Farbe, ein Gebiet, das in $B$ liegt, ändert seine Farbe. Wir behaupten, dass diese neue Färbung die Bedingung erfüllt. Es seien dazu $R$ und $S$ benachbarte Gebiete, es sei $G$ die Gerade, die eine Grenze zwischen $R$ und $S$ bildet. Bei  $G\ne H$  liegen beide Gebiete in $A$ oder in $B$ und die beiden Gebiete waren in der alten Situation schon Teile von benachbarten Gebieten. Wenn beide in $A$ liegen, so hatten sie in der alten Färbung verschiedene Farben, und dies wurde übernommen. Wenn beide in $B$ liegen, so hatten sie in der alten Färbung verschiedene Farben, und diese wurden jeweils verändert, die Farben sind also auch in der neuen Färbung verschieden. Bei  $G=H$  entstanden die Gebiete aus einem alten Gebiet durch die Trennung mit der neuen Geraden. In der alten Färbung hatten sie (als Teil eines gemeinsamen Gebietes) die gleiche Farbe. Eines der Gebiete liegt in $A$ und eines in $B$, d.h., eines behält seine Farbe und eines wird umgefärbt, die Farben in der neuen Färbung sind also verschieden.