Kurs:Diskrete Mathematik/22/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	3	0	0	0	0	0	3	0	0	0	0	0	0	0	0	0	12

Aufgabe (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein gemeinsamer Teiler von natürlichen Zahlen ${}a_{1},\ldots ,a_{k}$.
2. Ein Infimum zu einer Teilmenge  ${}J\subseteq I$  in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Ein Verband ${}M$.
4. Der Kantengraph zu einem Graphen  ${}G=(V,E)$. 
5. Ein Weg in einem Graphen.
6. Ein planarer Graph.

Lösung

1. Eine natürliche Zahl ${}t$ heißt gemeinsamer Teiler der ${}a_{1},\ldots ,a_{k}$, wenn ${}t$ jedes ${}a_{i}$ teilt für ${}i=1,\ldots ,k$.
2. Ein Element  ${}s\in I$  heißt Infimum von ${}J$, wenn ${}s$ die größte untere Schranke von ${}J$ ist.
3. Ein Verband ist eine geordnete Menge ${}(M,\leq )$ mit der Eigenschaft, dass für je zwei Elemente  ${}x,y\in M$  ein Infimum ${}x\sqcap y$ und ein Supremum ${}x\sqcup y$ existiert.
4. Der Kantengraph ist derjenige Graph, dessen Knotenmenge die Kantenmenge ${}E$ von ${}G$ ist und bei dem zwei Knoten ${}L_{1}$ und ${}L_{2}$ (also Kanten aus ${}G$) genau dann durch eine Kante verbunden werden, wenn ${}L_{1}$ und ${}L_{2}$ einen gemeinsamen Punkt in ${}V$ besitzen.
5. Ein Weg ist eine Folge ${}v_{1},v_{2},\ldots ,v_{m}$ von Knoten derart, dass ${}v_{i}v_{i+1}$ für alle ${}i$ eine Kante ist.
6. Ein Graph heißt planar, wenn er eine geometrische Realisierung im ${}\mathbb {R} ^{2}$ besitzt.

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 (0 Punkte)

Lösung erstellen

Aufgabe (3 Punkte)

Es sei ${}M$ eine endliche Menge und ${}\varphi \colon M\rightarrow M$ eine Abbildung. Es sei ${}\varphi ^{n}$ die ${}n$-fache Hintereinanderschaltung von ${}\varphi$ mit sich selbst. Zeige, dass es natürliche Zahlen  ${}m>n\geq 1$  mit  ${}\varphi ^{n}=\varphi ^{m}$  gibt.

Lösung

Da ${}M$ endlich ist, ist auch die Abbildungsmenge ${}\operatorname {Abb} \,{\left(M,M\right)}$ endlich, da es für jedes Element nur ${}{\#\left(M\right)}$ viele Möglichkeiten gibt, wohin es abgebildet werden kann. Die Hintereinanderschaltungen ${}\varphi ^{n}$, ${}n\in \mathbb {N}$, gehören alle zu dieser Abbildungsmenge. Da es keine injektive Abbildung von ${}\mathbb {N} _{+}$ in eine endliche Menge gibt, gibt es Zahlen  ${}m\neq n$  mit

${}\varphi ^{m}=\varphi ^{n}\,.$

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 (3 Punkte)

Bestimme in ${}\mathbb {Z}$ mit Hilfe des euklidischen Algorithmus den größten gemeinsamen Teiler von ${}10868$ und ${}9243$.

Lösung

Der Euklidische Algorithmus liefert:

$10868=1\cdot 9243+1625$

$9243=4\cdot 1625+1118$

$1625=1\cdot 1118+507$

$1118=2\cdot 507+104$

$507=4\cdot 104+91$

$104=1\cdot 91+13$

$91=7\cdot 13+0.$

Der größte gemeinsame Teiler von ${}10868$ und ${}9243$ ist also ${}13$.

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 (0 Punkte)

Lösung erstellen

Aufgabe (0 Punkte)

Lösung erstellen