Kurs:Diskrete Mathematik/3/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Fakultät einer natürlichen Zahl ${}n$.
2. Eine linksvollständige Relation ${}R\subseteq M\times N$.
3. Eine obere Schranke zu einer Teilmenge ${}J\subseteq I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
4. Ein starrer Graph.
5. Die Lapace-Matrix zu einem Multigraphen ${}G$.
6. Die chromatische Zahl eines Graphen.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl in der Potenzmenge zu einer endlichen Menge.
2. Der Satz über die Beschreibung des Durchschnitts von Untergruppen von ${}\mathbb {Z}$.
3. Der Fünf-Farben-Satz.

Aufgabe * (2 Punkte)

Ein Mann steht mit einem Wolf, einer Ziege und einem Kohl am Ufer eines Flusses und möchte diesen überqueren. Es steht ein Boot zur Verfügung, in dem neben ihm nur ein weiterer Passagier Platz hat. Wie kann er den Fluss überqueren, ohne dass dabei der Wolf die Ziege oder die Ziege den Kohl frisst?

Aufgabe * (6 Punkte)

Beweise den Satz über die Wohldefiniertheit der Anzahl einer endlichen Menge.

Aufgabe * (2 Punkte)

Auf wie viele Arten kann man mit den üblichen Münzen einen Betrag von ${}10$ Cent begleichen?

Aufgabe * (3 (1.5+1.5) Punkte)

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 (in beide Richtungen).

1. Wie vielen entgegenkommenden Schiffen begegnet der Zug?
2. Wie viele Schiffe überholt der Zug?

Aufgabe * (4 Punkte)

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 (die Reihenfolge ist aber egal), die beiden Ballstationen (Basketballkorb und Medizinball) sollen aber nicht unmittelbar hintereinander absolviert werden.

Wie viele Möglichkeiten (Reihenfolgen) gibt es für einen vollständigen Durchlauf, wenn diese beiden Bedingungen erfüllt sein sollen?

Aufgabe * (3 Punkte)

Beweise die folgende Form des allgemeinen Distributivgesetzes für einen kommutativen Halbring ${}R$ durch Induktion über ${}k$, wobei der Fall ${}k=2$ verwendet werden darf (dabei sind ${}n_{1},\ldots ,n_{k}$ natürliche Zahlen und ${}a_{j,i}\in R$).

${}{\begin{aligned}{\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}}\\\end{aligned}}$

Aufgabe (0 Punkte)

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

Die Karte zeigt Österreich mit seinen Bundesländern und den zugehörigen Hauptstädten (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 (Nachbarschaftsbeziehung) beschreibt. Dabei legen wir fest, dass ein Land auch zu sich selbst benachbart ist.

1. Welche Eigenschaften einer Äquivalenzrelation erfüllt diese Relation?
2. Bestimme die Faser zu Kärnten.
3. Gibt es eine Kette ${}x_{1},x_{2},\ldots ,x_{n}$ in ${}M$ mit ${}x_{i}Rx_{i+1}$ für alle ${}i$, bei der jedes Bundesland genau einmal vorkommt?

Aufgabe (0 Punkte)

Aufgabe * (4 Punkte)

Beweise das Lemma von Euklid für ganze Zahlen.

Aufgabe (0 Punkte)

Aufgabe * (3 Punkte)

Bestimme das inverse Element zu ${}{\overline {55}}$ in ${}\mathbb {Z} /(93)$.

Aufgabe * (3 Punkte)

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen und sei

$f\colon M\longrightarrow N$

eine surjektive Abbildung. Wie viele Abbildungen

$s\colon N\longrightarrow M$

mit

${}f\circ s=\operatorname {Id} _{N}\,$

gibt es?

Aufgabe * (4 (2+2) Punkte)

Es sei ${}\varphi \colon G\rightarrow H$ ein Graphhomomorphismus.

1. Es sei ${}\varphi$ injektiv. Zeige, dass für den Grad die Abschätzung

   ${}d(P)\leq d(\varphi (P))\,$

   für jeden Punkt ${}P\in G$ gilt.

2. Wie sieht es aus, wenn ${}\varphi$ nicht injektiv ist?

Aufgabe * (3 (1.5+1.5) Punkte)

Wir betrachten den Spielzuggraphen zum Läufer beim Schach auf einem ${}3\times 3$-Brett wie abgebildet.

1. Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.
2. Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

Aufgabe (0 Punkte)

Aufgabe (1 Punkt)

Begründe, dass der abgebildete Graph hamiltonsch ist.