Kurs:Diskrete Mathematik/3/Klausur/kontrolle

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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

Aufgabe * (3 (1.5+1.5) Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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

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)Referenznummer erstellen

Aufgabe * (4 Punkte)Referenznummer erstellen

Beweise das Lemma von Euklid für ganze Zahlen.

Aufgabe (0 Punkte)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

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

Aufgabe * (3 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Aufgabe (1 Punkt)Referenznummer erstellen

Begründe, dass der abgebildete Graph hamiltonsch ist.