Kurs:Diskrete Mathematik/13/Klausur/kontrolle

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)Referenznummer erstellen

Aufgabe * (3 Punkte)Referenznummer erstellen

Aufgabe * (2 Punkte)Referenznummer erstellen

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

Aufgabe * (4 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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

Aufgabe * (2 Punkte)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

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)Referenznummer erstellen

Bestimme die Automorphismengruppe des abgebildeten Graphen.

Aufgabe * (4 Punkte)Referenznummer erstellen

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

Aufgabe * (10 Punkte)Referenznummer erstellen

Beweise den Paarungssatz (Heiratssatz).

Aufgabe * (4 Punkte)Referenznummer erstellen

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

Aufgabe * (4 Punkte)Referenznummer erstellen

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