Kurs:Diskrete Mathematik/2/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein Monoid ${}M$.
2. Der größte gemeinsame Teiler von natürlichen Zahlen ${}a_{1},\ldots ,a_{k}$.
3. Die Äquivalenzrelation ${}\sim _{H}$ zu einer Untergruppe ${}H\subseteq G$ in einer kommutativen Gruppe.
4. Ein Graphisomorphismus ${}\varphi \colon G\rightarrow H$.
5. Ein vollständiger bipartiter Graph.
6. Die Paarungsbedingung für ${}A$ in einem bipartiten Graphen ${}G$ mit ${}V=A\uplus B$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Urbildanzahl.
2. Der Hauptsatz der elementaren Zahlentheorie.
3. Der Charakterisierungssatz für Bäume.

Aufgabe * (2 Punkte)

Zwei Personen wollen ihre Körpergröße vergleichen. Sie können sich direkt vergleichen, indem sie sich Rücken an Rücken hinstellen, oder, indem sie ein Maßband (Zollstock) nehmen und ihre Größe damit jeweils messen. Welche Analogien zu diesen Methoden gibt es, wenn man zwei endliche Mengen vergleichen möchte?

Aufgabe * (2 Punkte)

Es findet das olympische 100-Meter-Finale mit acht Teilnehmern statt. Sie wissen, welche drei Teilnehmer eine Medaille gewinnen (aber nicht, wer welche Medaille gewinnt). Wie viele Möglichkeiten für das Gesamtergebnis aller acht Teilnehmer verbleiben (keine Platzierung ist doppelt besetzt)?

Aufgabe * (4 (2+2) Punkte)

Es sei ${}S=\{0,1\}$. Betrachte das Monoid ${}M$, das aus allen Abbildungen von ${}S$ nach ${}S$ besteht mit der Hintereinanderschaltung ${}\circ$ von Abbildungen als Verknüpfung.

1. Beschreibe die Elemente in ${}M$ und erstelle eine Verknüpfungstabelle für ${}M$.
2. Bestimme sämtliche Untermonoide von ${}M$ und entscheide jeweils, ob sie kommutativ sind und ob es sich um Gruppen handelt.

Aufgabe * (3 Punkte)

Beweise die Nichtnullteilereigenschaft für einen Körper ${}K$.

Aufgabe * (4 Punkte)

Es sei ${}M$ eine Menge und ${}P$ die Potenzmenge von ${}M$. Betrachte die Relation ${}T$ auf ${}P$, die durch

$T(A,B){\text{ genau dann, wenn }}A\subseteq B$

gegeben ist (dabei sind also ${}A$ und ${}B$ Teilmengen von ${}M$). Bestimme die Anzahl der Elemente dieser Relation, wenn ${}M$ ${}n$ Elemente besitzt.

Aufgabe (1 Punkt)

Skizziere den Graphen der Addition

$+\colon \mathbb {R} \times \mathbb {R} \longrightarrow \mathbb {R} ,\,(x,y)\longmapsto x+y.$

Aufgabe * (2 Punkte)

Es sei ${}M=\operatorname {Abb} \,{\left(\mathbb {R} ,\mathbb {R} \right)}$ die Menge aller Abbildungen von ${}\mathbb {R}$ nach ${}\mathbb {R}$. Wir definieren auf ${}M$ die Relation

${}f\preccurlyeq g\,,$

falls es ein ${}a\in \mathbb {R}$ derart gibt, dass

${}f(x)\leq g(x)\,$

für alle ${}x\geq a$ gilt. Welche Eigenschaften einer Ordnungsrelation sind erfüllt, welche nicht?

Aufgabe * (3 Punkte)

Zeige, dass in einem (ordnungstheoretischen) Verband ${}V$ das Absorptionsgesetz

${}x\sqcup (x\sqcap y)=x\,$

für alle ${}x,y\in V$ gilt.

Aufgabe * (4 Punkte)

Beweise das Kernkriterium für die Injektivität eines Gruppenhomomorphismus

$\varphi \colon G\longrightarrow H.$

Aufgabe * (3 Punkte)

Man bestimme den größten gemeinsamen Teiler von ${}3146$ und ${}1515$ und man gebe eine Darstellung des ${}\operatorname {ggT}$ von ${}3146$ und ${}1515$ mittels dieser Zahlen an.

Aufgabe * (5 Punkte)

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

${}{\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}}\,.$

Aufgabe (1 Punkt)

Lege in der Skizze für die drei Häuser überschneidungsfrei Wege zu den zugehörigen gleichfarbigen Gartentoren an.

Aufgabe * (8 (2+2+1+1+1+1) Punkte)

Wir betrachten den folgenden Graphen. Die Knotenmenge besteht aus den Zahlen von ${}10$ bis ${}99$, und zwei Zahlen werden genau dann durch eine Kante verbunden, wenn sie in genau einer Ziffer (an der richtigen Stelle) übereinstimmen.

1. Bestimme den Grad zu jedem Punkt des Graphen.
2. Wie viele Knoten und wie viele Kanten besitzt der Graph?
3. Was ist der Durchmesser des Graphen?
4. Was ist der Radius des Graphen?
5. Gibt es einen Graphautomorphismus, der die ${}21$ in die ${}12$ überführt und die ${}23$ auf sich selbst?
6. Ist die Vertauschung von Einer- und Zehnerziffer ein Graphautomorphismus?

Aufgabe * (1 Punkt)

Bestimme die Adjazenzmatrix zum abgebildeten Graphen.

Aufgabe * (5 Punkte)

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

Aufgabe * (2 Punkte)

Es sei ${}G$ ein Graph und ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus in einen bipartiten Graphen ${}H$. Zeige, dass ${}G$ ebenfalls bipartit ist.

Aufgabe * (2 Punkte)

Zeige, dass man im Satz von Berge nicht darauf verzichten kann, dass die Endpunkte der alternierenden Wege verschieden sind.

Aufgabe * (2 Punkte)

Ist es möglich, die Karte der deutschen Bundesländer mit drei Farben zulässig einzufärben?

Aufgabe * (4 Punkte)

Zeige durch Induktion über ${}n$, dass das chromatische Polynom eines Rundganges mit ${}n$ Knoten gleich ${}(X-1)^{n}+(-1)^{n}(X-1)$ ist.