Kurs:Diskrete Mathematik/8/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein inverses Element zu einem Element ${}x\in M$ bezüglich einer Verknüpfung

   $\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

   mit einem neutralen Element ${}e\in M$.

2. Eine lineare (oder totale) Ordnung ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Ein distributiver Verband ${}M$.
4. Ein ungerichteter Graph auf einer Menge ${}V$.
5. Eine Basis in einem Matroid ${}{\mathcal {M}}$.
6. Ein alternierender Weg bezüglich einer Paarung ${}P$ eines Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von Abbildungen zwischen endlichen Mengen.
2. Der Satz über die Nichtnullteilereigenschaft in einem Körper ${}K$.
3. Der Charakterisierungssatz für eulersche Graphen.

Aufgabe * (5 Punkte)

Es sei ${}G$ eine Menge, die als disjunkte Vereinigung

${}G=A\uplus B\,$

gegeben ist. Definiere eine Bijektion zwischen der Potenzmenge ${}{\mathfrak {P}}\,(G)$ und der Produktmenge ${}{\mathfrak {P}}\,(A)\times {\mathfrak {P}}\,(B)$.

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

Zur großen Pause fährt der Eiswagen „Largo Maggiore“ auf den Pausenhof. Eisverkäufer Lorenzo di Napoli bietet ${}10$ Eissorten an. Lucy Sonnenschein hat heute Lust auf ein Eis mit drei Kugeln, die in der Eistüte übereinander gestapelt werden.

1. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge mitberücksichtigt wird?
2. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Lucy drei verschiedene Sorten möchte und die Schleckreihenfolge nicht mitberücksichtigt wird?
3. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge mitberücksichtigt wird?
4. Wie viele Möglichkeiten gibt es für diesen Eiskauf, wenn Sorten mehrfach auftreten dürfen und die Schleckreihenfolge nicht mitberücksichtigt wird?
5. Wie kann man mit den Schritten mit denen man (4) beantwortet hat die Antworten zu (1) und zu (3) herleiten?

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

1. Skizziere vier Geraden im Raum mit der Eigenschaft, dass es insgesamt zwei Schnittpunkte gibt.
2. Skizziere vier Geraden in der Ebene mit der Eigenschaft, dass es insgesamt drei Schnittpunkte gibt.
3. Zeige, dass es in der Ebene nicht vier Geraden geben kann, die insgesamt zwei Schnittpunkte besitzen.

Aufgabe * (2 Punkte)

Beweise den Satz über das inverse Element in einer Gruppe ${}(G,\circ ,e)$.

Aufgabe * (1 Punkt)

Bestimme die Primfaktorzerlegung von

${\binom {15}{5}}.$

Aufgabe * (7 Punkte)

Es stehen zwei Eimer ohne Markierungen zur Verfügung, ferner eine Wasserquelle. Der eine Eimer hat ein Fassungsvermögen von ${}a$ und der andere ein Fassungsvermögen von ${}b$ Litern, wobei ${}a$ und ${}b$ teilerfremd seien. Zeige, dass man allein durch Auffüllungen, Ausleerungen und Umschüttungen erreichen kann, dass in einem Eimer genau ein Liter Wasser enthalten ist.

Aufgabe * (6 Punkte)

Beweise den Satz über die atomare Darstellung in einem booleschen Verband.

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

Es sei ${}\leq _{1}$ eine Ordnungsrelation auf einer Menge ${}M_{1}$ und ${}\leq _{2}$ eine Ordnungsrelation auf einer Menge ${}M_{2}$, die zueinander mittels der beiden bijektiven Abbildungen

$\varphi ,\psi \colon M_{1}\longrightarrow M_{2}$

isomorph seien. Es gilt also ${}x\leq _{1}y$ (in ${}M_{1}$) genau dann, wenn ${}\varphi (x)\leq _{2}\psi (y)$ (in ${}M_{2}$) gilt.

1. Zeige, dass ${}\varphi$ ordnungstreu ist.
2. Zeige, dass ${}\varphi$ ordnungsvolltreu ist.
3. Zeige, dass ${}\left(M_{1},\leq _{1}\right)$ und ${}\left(M_{2},\leq _{2}\right)$ zueinander konjugiert-isomorph sind.

Aufgabe (1 Punkt)

Es sei ${}G$ der lineare Graph mit ${}7$ Knoten. Skizziere für die möglichen Wurzeln den Graphen ${}G$ derart, dass die Wurzel oben platziert ist und dass der Abstand eines Punktes zur Wurzel direkt über die Höhe der Platzierung erkennbar ist.

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

Es sei ${}G$ ein zusammenhängender Graph mit Durchmesser ${}d$.

1. Zeige, dass es in ${}G$ einen Unterbaum gibt, dessen Durchmesser ebenfalls ${}d$ ist.
2. Zeige, dass in ${}G$ jeder aufspannende Baum einen Durchmesser ${}\geq d$ besitzt.
3. Man gebe ein Beispiel für einen zusammenhängenden Graphen ${}G$ derart, dass jeder aufspannende Baum einen Durchmesser ${}>d$ besitzt.

Aufgabe * (5 (3+2) Punkte)

Es sei ${}G$ ein Graph mit ${}n$ Knotenpunkten.

1. Zeige, dass das charakteristische Polynom die Form

   $x^{n}+c_{n-2}x^{n-2}\ldots$

   besitzt.

2. Zeige, dass die Summe der Eigenwerte der Adjazenzmatrix (mit ihren algebraischen Vielfachheiten gezählt) gleich ${}0$ ist.

Aufgabe * (1 Punkt)

Skizziere einen Graphen, der nicht bipartit ist und in dem es keinen Kreis der Länge ${}3$ gibt.

Aufgabe * (7 Punkte)

Beweise die eulersche Polyederformel.