Kurs:Diskrete Mathematik/24/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	2	3	0	0	0	0	0	0	0	0	0	11

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

Die Assoziativität einer Verknüpfung
$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y.$
Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$ .
Die Äquivalenzklasse zu einem Element ${}x\in M$ in einer Menge ${}M$ mit einer Äquivalenzrelation ${}\sim$ .
Ungerichteter Graph/Automorphismus/Definition/Begriff
Graph/Adjazenzmatrix/Charakteristisches Polynom/Definition/Begriff
Ein Hamiltonkreis.

Lösung

Eine Verknüpfung
$\circ \colon M\times M\longrightarrow M,\,(x,y)\longmapsto x\circ y,$

heißt assoziativ, wenn für alle ${}x,y,z\in M$ die Gleichheit

${}(x\circ y)\circ z=x\circ (y\circ z)\,$

gilt.
Die Relation ${}\preccurlyeq$ ${}\preccurlyeq$ heißt Ordnungsrelation, wenn folgende drei Bedingungen erfüllt sind.
1. Es ist ${}i\preccurlyeq i$ für alle ${}i\in I$ .
2. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq k$ folgt stets ${}i\preccurlyeq k$ .
3. Aus ${}i\preccurlyeq j$ und ${}j\preccurlyeq i$ folgt ${}i=j$ .
Die Äquivalenzklasse zu ${}x$ ist die Menge
${}[x]={\left\{y\in M\mid y\sim x\right\}}\,.$
Ungerichteter Graph/Automorphismus/Definition/Begriff/Inhalt
Graph/Adjazenzmatrix/Charakteristisches Polynom/Definition/Begriff/Inhalt
Graph/Hamiltonkreis/Definition/Begriff/Inhalt

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

Lösung

Aufgabe (2 (1+1) Punkte)

Es seien ${}a,m,n$ natürliche Zahlen mit ${}a\geq 1$ .

Bestimme ${}\operatorname {ggT} (a^{m},a^{n})$ .
Bestimme ${}\operatorname {kgV} (a^{m},a^{n})$ .

Lösung

Es sei

{}n\geq m\,.

Dann ist

{}a^{n}=a^{m+n-m}=a^{m}\cdot a^{n-m}\,

und somit ist ${}a^{m}$ ein Teiler von ${}a^{n}$ . In einem solchen Fall ist der Teiler der größte gemeinsame Teiler und das Vielfache das kleinste gemeinsame Vielfache. Also ist

{}\operatorname {ggT} (a^{m},a^{n})=a^{m}\,

und

{}\operatorname {kgV} (a^{m},a^{n})=a^{n}\,.

Aufgabe (3 Punkte)

Führe in ${}\mathbb {Z} /(7)[X]$ die Division mit Rest „ ${}P$ durch ${}T$ “ für die beiden Polynome ${}P=2X^{3}+4X^{2}+5$ und ${}T=3X^{2}+X+1$ durch.