Kurs:Diskrete Mathematik/2/Klausur/kontrolle

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

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

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

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

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

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

Aufgabe * (4 Punkte)Referenznummer erstellen

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

Skizziere den Graphen der Addition

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

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

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

$\varphi \colon G\longrightarrow H.$

Aufgabe * (3 Punkte)Referenznummer erstellen

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

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

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

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

Bestimme die Adjazenzmatrix zum abgebildeten Graphen.

Aufgabe * (5 Punkte)Referenznummer erstellen

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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

Aufgabe * (4 Punkte)Referenznummer erstellen

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