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	2	0	0	0	0	0	2	3	0	0	0	0	4	0	0	0	0	17

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Die Assoziativität einer Verknüpfung

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

2. Eine Ordnungsrelation ${}\preccurlyeq$ auf einer Menge ${}I$.
3. Die Äquivalenzklasse zu einem Element ${}x\in M$ in einer Menge ${}M$ mit einer Äquivalenzrelation ${}\sim$.
4. Ein Automorphismus eines Graphen ${}G=(V,E)$.
5. Das charakteristische Polynom zu einem Graphen ${}G$.
6. Ein Hamiltonkreis in einem Graphen ${}(V,E)$.

Lösung

1. 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.

2. Die Relation ${}\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$.
3. Die Äquivalenzklasse zu ${}x$ ist die Menge

   ${}[x]={\left\{y\in M\mid y\sim x\right\}}\,.$

4. Ein Automorphismus ist ein Isomorphismus ${}\varphi \colon G\rightarrow G$.
5. Das charakteristische Polynom von ${}G$ ist das charakteristische Polynom der Adjazenzmatrix von ${}G$.
6. Ein Hamiltonkreis ist ein Kreis, in dem jeder Knotenpunkt vorkommt.

Aufgabe (3 Punkte)

Formuliere die folgenden Sätze.

1. /Fakt/Name
2. /Fakt/Name
3. /Fakt/Name

Lösung

1. /Fakt
2. /Fakt
3. /Fakt

Aufgabe (2 Punkte)

Professor Knopfloch und Dr. Eisenbeis stehen am Ufer des Rubbenbruchsees und können sich nicht einigen, ob sie mit dem oder gegen den Uhrzeigersinn drumrum laufen sollen. Deshalb läuft Professor Knopfloch gegen den Uhrzeigersinn und Dr. Eisenbeis mit dem Uhrzeigersinn. Das Verhältnis ihrer Geschwindigkeiten ist ${}5:4$, und daher läuft Knopfloch fünfmal um den See und Eisenbeis viermal um den See. Wie oft begegnen sie sich (Begegnung ganz am Anfang und am Ende mitzählen)?

Lösung

Die erste Begegnung (nach der Begegnung am Start) findet statt, wenn Knopfloch ${}{\frac {5}{9}}$ und Eisenbeis ${}{\frac {4}{9}}$ des Sees umrundet haben. Dieser Rhythmus bleibt konstant, d.h. Eisenbeis begegnet Knopfloch stets nach einer Wegstrecke von ${}{\frac {4}{9}}$ des Seeumfanges. Da sie viermal den See umrundet, sind das insgesamt ${}10$ Begegnungen (${\frac {0}{9}},{\frac {4}{9}},{\frac {8}{9}},\ldots ,{\frac {36}{9}}$).

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 (2 (1+1) Punkte)

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

1. Bestimme ${}\operatorname {ggT} (a^{m},a^{n})$.
2. 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.

Lösung

Es ist

${}2X^{3}+4X^{2}+5={\left(3X^{2}+X+1\right)}{\left(3X+5\right)}+6X\,.$

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)

Zeige, dass ein gerichteter Graph genau dann symmetrisch ist, wenn für jede Teilmenge ${}T\subseteq M$ die Beziehung

${}T\subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,$

gilt.

Lösung

Wir zeigen, dass die Negationen der beiden Eigenschaften zueinander äquivalent sind.

Es sei zuerst die Relation nicht symmetrisch. Dann gibt es ${}x,y$ mit ${}xRy$, aber ${}yRx$ gilt nicht. Dann ist ${}y$ kein Vorgänger von ${}x$ und daher ist ${}y\in M\setminus \operatorname {Vorg} {\left(\{x\}\right)}$. Es ist somit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$ und also ${}x\notin M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(\{x\}\right)}\right)}$. Daher gilt die Vorgängereigenschaft für

${}T=\{x\}\,$

nicht.

Es sei nun die Vorgängereigenschaft nicht erfüllt, es gebe also eine Teilmenge ${}T\subseteq M$ mit

${}T\not \subseteq M\setminus \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}\,.$

Dann gibt es ein ${}x\in T$ mit ${}x\in \operatorname {Vorg} {\left(M\setminus \operatorname {Vorg} {\left(T\right)}\right)}$. Dies bedeutet, dass es ein ${}y\in M\setminus \operatorname {Vorg} {\left(T\right)}$ mit ${}xRy$ gibt. Wegen ${}y\notin \operatorname {Vorg} {\left(T\right)}$ ist insbesondere nicht ${}yRx$, also ist die Relation nicht symmetrisch.

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen