Kurs:Diskrete Mathematik/23/Klausur mit Lösungen

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

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Eine antimonotone Abbildung
$F\colon M_{1}\longrightarrow M_{2},$

zwischen den geordneten Mengen ${}(M_{1},\leq _{1})$ und ${}(M_{2},\leq _{2})$ .
Der Multinomialkoeffizient
${\binom {n}{r_{1},\dotsc ,r_{k}}}$

${}n$ über ${}r_{1},\ldots ,r_{k}$ .
Der Grad eines Punktes ${}v\in V$ in einem Graphen ${}G=(V,E)$ .
Ein zusammenhängender Graph ${}(V,E)$ .
Ein bipartiter Graph ${}G=(V,E)$ .
Die Eigenschaft einer Paarung ${}P$ in einem Graphen ${}G=(V,E)$ , einen Knotenpunkt ${}v\in V$ abzudecken.

Lösung

Die Abbildung
$F\colon M_{1}\longrightarrow M_{2},$

heißt ordnungstreu, wenn für alle ${}x,x'\in M_{1}$ mit ${}x\leq _{1}x'$ stets ${}F(x)\geq _{2}F(x')$ gilt.
Der Multinomialkoeffizient ist
${}{\binom {n}{r_{1},\dotsc ,r_{k}}}:={\frac {n!}{r_{1}!\cdots r_{k}!}}\,.$
Der Grad eines Punktes in einem ungerichteten Graphen ist die Anzahl seiner Nachbarn.
Ein Graph heißt zusammenhängend, wenn es zu je zwei Punkten ${}u,v\in G$ einen Weg gibt, der ${}u$ und ${}v$ verbindet.
Ein Graph heißt bipartit, wenn es eine disjunkte Zerlegung
${}V=A\uplus B\,$

derart gibt, dass es nur Kanten zwischen ${}A$ und ${}B$ gibt.
Die Paarung ${}P$ deckt ${}v$ ab, wenn es eine Kante aus ${}P$ gibt, zu der ${}v$ gehört.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Lösung

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (4 Punkte)

Es sei ${}n\in \mathbb {N}$ und ${}\mathbb {Z} /(n)$ der zugehörige Restklassenring. Zeige, dass ${}a\in \mathbb {Z}$ genau dann eine Einheit modulo ${}n$ ist, wenn ${}a$ und ${}n$ teilerfremd sind.

Lösung

Sind ${}a$ und ${}n$ teilerfremd, so gibt es nach Satz 6.1 (Diskrete Mathematik (Osnabrück 2020)) eine Darstellung der ${}1$ , es gibt also ganze Zahlen ${}r,s$ mit

{}ra+sn=1\,.

Betrachtet man diese Gleichung modulo ${}n$ , so ergibt sich ${}ra=1$ in ${}\mathbb {Z} /(n)$ . Damit ist ${}a$ eine Einheit mit dem inversen Element ${}a^{-1}=r$ .

Ist umgekehrt ${}a$ eine Einheit in ${}\mathbb {Z} /(n)$ , so gibt es ein ${}r\in \mathbb {Z} /(n)$ mit ${}ar=1$ in ${}\mathbb {Z} /(n)$ . Das bedeutet aber, dass ${}ar-1$ ein Vielfaches von ${}n$ ist, sodass also