Kurs:Diskrete Mathematik/3/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Die Fakultät einer natürlichen Zahl $n$ .
Eine linksvollständige Relation $R \subseteq M \times N$ .
Eine obere Schranke zu einer Teilmenge $J \subseteq I$ in einer geordneten Menge $(I, ≼)$ .
Der Typ einer Permutation $π$ auf einer endlichen Menge $M$ .
Die Lapace-Matrix zu einem Multigraphen $G$ .
Die chromatische Zahl eines Graphen.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

Der Satz über die Anzahl in der Potenzmenge zu einer endlichen Menge.
Der Satz über die Beschreibung des Durchschnitts von Untergruppen von $ℤ$ .
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 * (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).

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

Aufgabe * (4 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}, \dots, n_{k}$ natürliche Zahlen und $a_{j, i} \in R$ ).

\begin{matrix} (\sum_{i_{1} = 1}^{n_{1}} a_{1, i_{1}}) \cdot (\sum_{i_{2} = 1}^{n_{2}} a_{2, i_{2}}) \dots (\sum_{i_{k} = 1}^{n_{k}} a_{k, i_{k}}) & = \sum_{(i_{1}, i_{2}, \dots, i_{k}) \in {1, \dots, n_{1}} \times {1, \dots, n_{2}} \times \dots \times {1, \dots, n_{k}}} a_{1, i_{1}} \cdot a_{2, i_{2}} \dots a_{k, i_{k}} . \end{matrix}

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.

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

Aufgabe * (4 Punkte)

Beweise das Lemma von Euklid für ganze Zahlen.

Aufgabe * (3 Punkte)

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

Aufgabe * (3 Punkte)

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

f : M ⟶ N

eine surjektive Abbildung. Wie viele Abbildungen

s : N ⟶ M

mit

f \circ s = {Id}_{N}

gibt es?

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

Es sei $\sim_{1}$ eine Äquivalenzrelation auf einer Menge $M$ und $\sim_{2}$ eine Äquivalenzrelation auf einer Menge $N$ , die zueinander mittels der beiden bijektiven Abbildungen

φ, ψ : M ⟶ N

isomorph seien. Es gilt also $x \sim_{1} y$ (in $M$ ) genau dann, wenn $φ (x) \sim_{2} ψ (y)$ (in $N$ ) gilt.

Zeige, dass $φ$ (und ebenso $ψ$ ) eine Äquivalenzklasse von $\sim_{1}$ in eine Äquivalenzklasse von $\sim_{2}$ abbildet (es gilt also $φ ([x]) = [φ (x)]$ ).
Zeige, dass $φ$ und $ψ$ jede Äquivalenzklasse von $\sim_{1}$ in die gleiche Äquivalenzklasse von $\sim_{2}$ abbildet.
Man gebe ein Beispiel, wo $φ \neq ψ$ ist.
Es seien $M, N$ endlich. Zeige, dass die beiden Äquivalenzrelationen sogar konjugiert-isomorph zueinander sind.

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

Wir betrachten die lineare Rekursion $x_{n} = 3 x_{n - 1} + 7 x_{n - 2}$ .

a) Erstelle die Rekursionsmatrix zu dieser Rekursion.

b) Bestimme das charakteristische Polynom zu dieser Rekursion.

c) Bestimme die Nullstellen des charakteristischen Polynoms.

d) Bestimme die Eigenvektoren zur Rekursionsmatrix.

e) Bestimme die explizite Lösung zu dieser Rekursion für die Anfangsglieder $x_{0} = 2$ und $x_{1} = - 5$ .

Aufgabe * (4 (2+2) Punkte)

Es sei $φ : G \to H$ ein Graphhomomorphismus.

Es sei $φ$ injektiv. Zeige, dass für den Grad die Abschätzung
$d (P) \leq d (φ (P))$

für jeden Punkt $P \in G$ gilt.
Wie sieht es aus, wenn $φ$ nicht injektiv ist?

Aufgabe (5 (1+1+1+2) Punkte)

Wir betrachten das Kladogramm der Artiodactyla als einen binären Baum $B$ .

Was ist die Exzentrizität der Wurzel Cetartiodactyla und was ist der Durchmesser von $B$ ?
Was ist der Abstand zwischen einem Wal (Cetacea) und einem Schwein (Suina)?
Zeige, dass jeder Graphautomorphismus von $B$ die Wurzel auf sich selbst oder auf die Kamele (Tylopoda) abbildet.
Bestimme die Automorphismengruppe von $B$ .

Aufgabe * (3 (1.5+1.5) Punkte)

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

a) Zeige, dass der Spielzuggraph zum weißfeldrigen Läufer bipartit ist.

b) Zeige, dass der Spielzuggraph zum schwarzfeldrigen Läufer nicht bipartit ist.

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

Man gebe ein Beispiel für einen zyklischen zusammenhängenden Graphen $G$ , der die folgenden Eigenschaften erfüllt.

$G$ ist hamiltonsch und eulersch.
$G$ ist hamiltonsch und nicht eulersch.
$G$ ist nicht hamiltonsch und eulersch.
$G$ ist weder hamiltonsch noch eulersch.