Kurs:Diskrete Mathematik/13/Klausur

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

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Der Graph zu einer Abbildung ${}F\colon L\rightarrow M$.
2. Ein maximales Element ${}x\in I$ in einer geordneten Menge ${}(I,\preccurlyeq )$.
3. Ein Verband (algebraische Definition).
4. Der Komplementärgraph zu einem Graphen ${}G=(V,E)$.
5. Ein Kreis in einem Graphen.
6. Ein Eulerscher Kantenzug in einem Graphen ${}G=(V,E)$.

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Anzahl von fixpunktfreien Permutationen.
2. Der Satz über die Gradsumme in einem Graphen.
3. Der Satz von Berge.

Aufgabe * (2 Punkte)

Am Weihnachtsbaum gibt es ${}10$ Kerzen. Berechne die Anzahl der Reihenfolgen, wie die Kerzen angezündet werden können.

Aufgabe * (4 Punkte)

Es sei ${}M$ eine ${}n$-elementige Menge. Zeige, dass die Anzahl der ${}k$-elementigen Teilmengen von ${}M$ gleich dem Binomialkoeffizienten

${\binom {n}{k}}$

ist.

Aufgabe * (2 Punkte)

Es seien ${}(M,*)$ und ${}(N,\circ )$ Mengen mit Verknüpfungen und es sei

$\varphi \colon M\longrightarrow N$

eine mit den Verknüpfungen verträgliche surjektive Abbildung, es gelte also

${}\varphi (x*y)=\varphi (x)\circ \varphi (y)\,.$

Die Verknüpfung auf ${}M$ sei assoziativ. Zeige, dass auch die Verknüpfung auf ${}N$ assoziativ ist.

Aufgabe * (4 (1+1+1+1) Punkte)

Es sei ${}(M,\preccurlyeq )$ eine nichtleere geordnete Menge. Wir betrachten die Relation ${}\prec$ auf ${}M$, die durch ${}x\prec y$, falls ${}x\preccurlyeq y$ und ${}x\neq y$ gilt, definiert ist.

1. Ist ${}\prec$ transitiv?
2. Ist ${}\prec$ reflexiv?
3. Charakterisiere, wann ${}\prec$ symmetrisch ist.
4. Ist ${}\prec$ antisymmetrisch?

Aufgabe * (3 Punkte)

Zeige, dass in einem booleschen Verband ${}V$ die Gleichheit ${}\neg (x\sqcap y)=\neg x\sqcup \neg y$ für alle ${}x,y\in V$ gilt.

Aufgabe * (4 Punkte)

Es seien ${}a_{1},\ldots ,a_{k}$ ganze Zahlen. Zeige, dass

${}\mathbb {Z} a_{1}\cap \mathbb {Z} a_{2}\cap \ldots \cap \mathbb {Z} a_{k}=\mathbb {Z} u\,$

ist, wobei ${}u$ das kleinste gemeinsame Vielfache der ${}a_{1},\ldots ,a_{k}$ ist.

Aufgabe * (6 (2+2+2) Punkte)

Es sei ${}K$ ein Körper und ${}V\neq 0$ ein endlichdimensionaler ${}K$- Vektorraum.

1. Wir betrachten auf ${}V$ die Relation ${}R$, die durch ${}uRv$ gegeben ist, falls es eine lineare Abbildung ${}\varphi \colon V\rightarrow V$ mit ${}\varphi (u)=v$ gibt. Welche Eigenschaften einer Äquivalenzrelation sind erfüllt, welche nicht?
2. Wir betrachten auf ${}V$ die Relation ${}S$, die durch ${}uSv$ gegeben ist, falls es eine bijektive lineare Abbildung ${}\varphi \colon V\rightarrow V$ mit ${}\varphi (u)=v$ gibt. Zeige, dass dies eine Äquivalenzrelation ist.
3. Bestimme die Äquivalenzklassen zur Äquivalenzrelation ${}S$ aus (2).

Aufgabe * (3 Punkte)

Bestimme das inverse Element zu ${}{\overline {35}}$ in ${}\mathbb {Z} /(101)$.

Aufgabe * (2 Punkte)

Es sei ${}M=\{1,2,3,4,5,6,7\}$ und ${}N=\{a,b,c,d\}$. Bestimme die Anzahl der surjektiven Abbildungen von ${}M$ nach ${}N$ mit der zusätzlichen Eigenschaft, dass jedes Element aus ${}N$ höchstens zweimal getroffen wird.

Aufgabe * (3 (0.5+1+0.5+1) Punkte)

Bestimme zum Netzgraphen ${}G$ der Metro Manila die folgenden graphentheoretischen Invarianten (dabei gelten Recto und Doroteo Jose als eine Station, EDSA und Taft Avenue gelten als eine Station, Araneta Center und Cubao gelten als eine Station. North Avenue und Roosevelt sind durch eine Kante verbunden).

1. Die Blätter von ${}G$.
2. Die Exzentrizität von Pureza.
3. Den Maximalgrad von ${}G$. In welchen Stationen wird er angenommen?
4. Die Taille von ${}G$.

Aufgabe * (2 Punkte)

Skizziere einen zusammenhängenden Graphen, in dem es genau einen Knoten mit dem Grad ${}2$, genau einen Knoten mit dem Grad ${}3$, genau einen Knoten mit dem Grad ${}4$, ... und genau einen Knoten mit dem Grad ${}8$ gibt.

Aufgabe * (2 Punkte)

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe * (4 Punkte)

Bestimme die Anzahl der Spannbäume des vollständigen Graphen zu ${}4$ Punkten mit Hilfe des Satzes von Kirchhoff.

Aufgabe * (10 Punkte)

Beweise den Paarungssatz (Heiratssatz).

Aufgabe * (4 Punkte)

Bestimme das chromatische Polynom zum vollständigen bipartiten Graphen ${}K_{2,s}$.

Aufgabe * (4 Punkte)

Für welche der Schachfiguren Turm, Läufer, Dame, König ist der Spielzuggraph zu einem ${}8\times 8$-Feld planar?