Kurs:Diskrete Mathematik/17/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Eine Gruppe.
2. Die Eigenschaft, dass eine natürliche Zahl ${}a$ eine natürliche Zahl ${}b$ teilt.
3. Ein komplementärer beschränkter Verband ${}M$.
4. Ein Sterngraph.
5. Ein Blatt  ${}v\in V$  eines Graphen.
6. Die Adjazenzmatrix zu einem Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Lösbarkeit von Gleichungen in einer Gruppe ${}G$.
2. Der Satz über die Darstellungsmöglichkeiten von natürlichen Zahlen mit Gewichten.
3. Der Satz über die kombinatorische Struktur einer Waldmenge.

Aufgabe (2 Punkte)

In einer U-Bahn-Station wird der Zugang und der Ausgang über eine elektronische Karte geregelt, die man an einen Sensor halten muss, damit sich die Schranke öffnet. Es gibt 5 Ausgänge, aber nur 2 Zugänge. Was haben sich die Leute dabei vermutlich gedacht?

Aufgabe * (3 Punkte)

Die Hochschule „Tellerrand“ bietet lediglich ${}4$ Fächer an, nämlich Hethitologie, Assyriologie, Ägyptologie und Semitistik. Sie bietet lediglich ${}2$-Fächer-Bachelor an in beliebiger Fächerkombination. Wie viele Fächerkombinationen gibt es (es wird nicht zwischen Erst- und Zweitfach unterschieden)? Skizziere ein Mengendiagramm, das die Studentenschaft mit ihren Fächern wiedergibt. Die zu einem Fach gehörenden Studenten und Studentinnen sollen dabei durch ein zusammenhängendes Gebiet dargestellt werden.

Aufgabe * (2 Punkte)

Gabi Hochster hat sich wieder über Frau Maier-Sengupta geärgert. Sie möchte sagen „Frau Maier-Sengupta ist unterbelichtet“, doch weil sie keinen neuen Vermerk kassieren will, ändert sie in dem Satz jeden Vokal (stellenweise) zu einem anderen Vokal (ohne Umlaute) und jeden Diphthong (für uns sind das au, ai und eu) zu einem anderen Diphthong. Wie viele Möglichkeiten gibt es dafür?

Aufgabe * (8 Punkte)

Es seien ${}L,M,N$ endliche Mengen mit ${}\ell ,m$ bzw. ${}n$ Elementen. Wir betrachten die Abbildung

$\Psi \colon \operatorname {Abb} \,{\left(L,M\right)}\times \operatorname {Abb} \,{\left(M,N\right)}\longrightarrow \operatorname {Abb} \,{\left(L,N\right)},\,(f,g)\longmapsto g\circ f,$

die durch die Hintereinanderschaltung von Abbildungen gegeben ist. Zeige, dass ${}\Psi$ genau dann surjektiv ist, wenn

${}m\geq \operatorname {min} \left(\ell ,\,n\right)\,$

ist.

Aufgabe * (3 Punkte)

Bei einem Zwei-Personen-Regel-Spiel (wie Schach) spielen zwei Personen (${}A$ und ${}B$) nach gewissen Regeln gegeneinander. Die Personen ziehen abwechselnd. Es ist klar, was eine Mattgewinnstellung für ${}A$ ist, da ist ${}A$ am Zug und kann ${}B$ schlagen und das Spiel ist beendet. Definiere rekursiv, was innerhalb der Menge ${}S$ aller Stellungen eine Gewinnstellung für ${}A$ (mit ${}A$ am Zug) ist.

Aufgabe * (3 Punkte)

Es sei ${}G$ eine Gruppe und  ${}g\in G$  ein Element, und seien  ${}m,n\in \mathbb {Z}$  ganze Zahlen. Zeige die folgenden Potenzgesetze.

1. Es ist  ${}g^{0}=e_{G}$. 
2. Es ist  ${}g^{m+n}=g^{m}g^{n}$. 

Aufgabe * (2 Punkte)

Finde zwei natürliche Zahlen, deren Summe ${}65$ und deren Produkt ${}1000$ ist.

Aufgabe * (2 Punkte)

Erläutere die Division mit Rest für natürliche Zahlen anhand zweier Eimer (das Fassungsvermögen der beiden Eimer sei ein Vielfaches von einem Liter).

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

Zeige, dass für natürliche Zahlen ${}a,b,g$ folgende Aussagen gelten.

1. Für teilerfremde ${}a,b$ ist

   ${}\operatorname {kgV} \,(a,b)=ab\,.$

2. Es gibt  ${}c,d\in \mathbb {Z}$  mit

   $a=c\cdot \operatorname {ggT} \,(a,b)\,\,{\text{ und }}\,\,b=d\cdot \operatorname {ggT} \,(a,b),$

   wobei ${}c,d$ teilerfremd sind.

3. Es ist

   ${}\operatorname {kgV} \,(ga,gb)=g\cdot \operatorname {kgV} \,(a,b)\,.$

4. Es ist

   ${}\operatorname {ggT} \,(a,b)\cdot \operatorname {kgV} \,(a,b)=ab\,.$

Aufgabe * (8 Punkte)

Beweise den Satz über die Charakterisierung von isomorphen Abbildungen zwischen endlichen Mengen.

Aufgabe * (2 Punkte)

Es sei ${}z\in {\mathbb {C} },\,\vert {z}\vert <1$. Bestimme und beweise eine Formel für die Reihe

$\sum _{k=0}^{\infty }(-1)^{k}z^{k}.$

Aufgabe (2 Punkte)

Es sei  ${}G=(V,E)$  ein Graph, versehen mit der Äquivalenzrelation auf der Knotenmenge ${}V$, die durch die Verbundenheit zwischen Knotenpunkten gegeben ist. Bestimme den Quotientengraphen.

Aufgabe (3 Punkte)

Zeige, dass der abgebildete Graph starr ist.

Aufgabe * (4 (2+2) Punkte)

Bei der WM 2026 nehmen ${}48$ Mannschaften teil, zunächst in ${}12$ Gruppen zu je ${}4$ Mannschaften, wobei jeder gegen jeden spielt. Danach qualifizieren sich ${}32$ Mannschaften für die weiterführenden Runden (aus jeder Gruppe mindestens ${}2$ und höchstens ${}3$), die im KO-System ausgeführt werden (wir ignorieren das Spiel um Platz ${}3$). Der zugehörige (Begegnungs-) Graph ${}G$ (den man erst vollständig nach dem Turnier beschreiben kann) besteht aus der Vertexmenge, deren Elemente die Mannschaften sind, und zwei Mannschaften werden durch eine Kante verbunden, wenn sie gegeneinander gespielt haben. Dabei ziehen wir nur eine Kante, auch wenn zwei Mannschaften zweimal gegeneinander spielen sollten.

1. Kann es außer den Vorrundengruppen einen Untergraphen mit vier Mannschaften geben, der vollständig ist?
2. Kann man die vollen Untergraphen zu den Vorrundengruppen graphentheoretisch identifizieren?

Aufgabe * (2 Punkte)

Es sei ${}E$ die Familie der folgenden Vektoren im ${}\mathbb {R} ^{2}$.

$(5,-3),\,(6,0),\,(1,2),\,(4,5),\,(3,6).$

Bestimme das Matroid, das durch die lineare Unabhängigkeit von Teilfamilien gegeben ist.

Aufgabe * (5 Punkte)

Es sei ${}G$ der Graph auf der Knotenmenge ${}\{a,b,c\}$ mit den Kanten ${}\{a,b\},\,\{a,c\},\,\{b,c\}$. Bestimme die Adjazenzmatrix ${}A$ zu ${}G$ sowie das charakteristische Polynom, die Eigenwerte mit Vielfachheiten und die Eigenräume zu ${}A$.