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.

Geordnete Mengen/Abbildung/Antimonoton/Definition/Begriff
Multinomialkoeffizient/Definition/Begriff
Der Grad eines Punktes ${}v\in V$ in einem Graphen ${}G=(V,E)$ .
Ungerichteter Graph/Zusammenhängend/Definition/Begriff
Ungerichteter Graph/Bipartit/Definition/Begriff
Ungerichter Graph/Paarung/Punktabdeckung/Definition/Begriff

Lösung

Geordnete Mengen/Abbildung/Antimonoton/Definition/Begriff/Inhalt
Multinomialkoeffizient/Definition/Begriff/Inhalt
Der Grad eines Punktes in einem ungerichteten Graphen ist die Anzahl seiner Nachbarn.
Ungerichteter Graph/Zusammenhängend/Definition/Begriff/Inhalt
Ungerichteter Graph/Bipartit/Definition/Begriff/Inhalt
Ungerichter Graph/Paarung/Punktabdeckung/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Lösung

Aufgabe (4 Punkte)

Es sei ${}n\in \mathbb {N}$ und ${}\mathbb {Z} /(n)$ der zugehörige Restklassenring. Zeige, dass ${}a\in \mathbb {Z}$ eine Einheit modulo ${}n$ genau dann 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 Inversem ${}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