Kurs:Diskrete Mathematik/11/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	3	4	3	2	4	4	10	4	3	3	5	4	2	3	2	64

Aufgabe * (3 Punkte)

Definiere die folgenden (kursiv gedruckten) Begriffe.

1. Ein kommutativer Ring ${}R$.
2. Eine Relation auf einer Menge ${}M$.
3. Die Folge der euklidischen Reste zu ganzen Zahlen ${}a,b$ mit  ${}b\neq 0$. 
4. Die Automorphismengruppe eines ungerichteten Graphen ${}G$.
5. Der Umfang eines zyklischen Graphen ${}G$.
6. Eine zulässige Färbung eines Graphen  ${}G=(V,E)$. 

Aufgabe * (3 Punkte)

Formuliere die folgenden Sätze.

1. Der Satz über die Beziehung zwischen der Addition und endlichen Mengen.
2. Der Satz über die Restklassenkörper von ${}\mathbb {Z}$.
3. Der Rekursionssatz für aufspannende Bäume.

Aufgabe * (2 Punkte)

Anna kann sich nicht zwischen Heinrich und Konrad entscheiden, deshalb lässt sie sich vom Zufall leiten. Sie wohnt an einer U-Bahn-Station der Linie ${}5$, die von Heinsheim nach Konsau fährt. Heinrich wohnt in Heinsheim und Konrad in Konsau. Wenn Anna Lust auf ein Date hat, geht sie einfach zu ihrer Station und nimmt die erstbeste U-Bahn, die gerade kommt. Die U-Bahnen fahren in beide Richtungen im Zehn-Minuten-Takt und die U-Bahnen nach Heinsheim fahren ${}:\!01,:\!11,:\!21$ etc. Nach einiger Zeit stellt Anna fest, dass sie Konrad viermal so häufig besucht wie Heinrich. Wann fahren die U-Bahnen nach Konsau ab?

Aufgabe * (3 Punkte)

Heinz-Peter schaut am Morgen in den Spiegel und entdeckt fünf Pickel auf seiner Stirn. Diese müssen alle ausgedrückt werden, wobei zwei Pickel so nah beieinander liegen, dass sie unmittelbar hintereinander behandelt werden müssen. Wie viele Reihenfolgen gibt es, die Pickel auszudrücken?

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

Wir betrachten den Binomialkoeffizienten als eine Verknüpfung

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(n,k)\longmapsto {\binom {n}{k}},$

wobei bei  ${}k>n$  der Binomialkoeffizient als ${}0$ zu interpretieren ist. Diese Verknüpfung ist offenbar nicht kommutativ.

a) Bestimme ${}{\binom {\binom {3}{2}}{1}}$ und ${}{\binom {3}{\binom {2}{1}}}$.

b) Besitzt diese Verknüpfung ein neutrales Element von links?

c) Besitzt diese Verknüpfung ein neutrales Element von rechts?

d) Ist diese Verknüpfung assoziativ?

Aufgabe (3 Punkte)

Es sei ${}M$ ein Monoid,  ${}a,b\in M$  und  ${}m,n\in \mathbb {N}$.  Zeige die folgenden Potenzgesetze.

1. ${}a^{m+n}=a^{m}\cdot a^{n}\,.$

2. ${}(a^{m})^{n}=a^{mn}\,.$

3. Wenn ${}M$ kommutativ ist, so ist

   ${}(a\cdot b)^{n}=a^{n}\cdot b^{n}\,.$

Aufgabe * (2 Punkte)

Bestimme für das Polynom

${}P=7X^{11}-3X^{8}+{\frac {3}{2}}X^{6}-X+5\,$

den Grad, den Leitkoeffizienten, den Leitterm und den Koeffizienten zu ${}X^{5}$.

Aufgabe * (4 Punkte)

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

Aufgabe * (4 Punkte)

Es sei ${}M$ eine Menge und ${}\preccurlyeq$ eine Ordnung auf ${}M$. Zeige durch Induktion über ${}n\geq 2$ die Aussage: Wenn für Elemente ${}a_{1},\ldots ,a_{n}\in M$ die Beziehungen

${}a_{1}\preccurlyeq a_{2}\preccurlyeq \ldots \preccurlyeq a_{n-1}\preccurlyeq a_{n}\,$

und

${}a_{n}\preccurlyeq a_{1}\,$

gelten, dann sind alle ${}a_{1},\ldots ,a_{n}$ gleich.

Aufgabe * (10 (3+3+4) Punkte)

Wir betrachten die Menge der natürlichen Zahlen mit den beiden Verknüpfungen

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto {\operatorname {GgT} \,\left(a,b\right)}$

und

$\mathbb {N} \times \mathbb {N} \longrightarrow \mathbb {N} ,\,(a,b)\longmapsto {\operatorname {KgV} \,\left(a,b\right)}.$

1. Zeige, dass der größte gemeinsame Teiler eine kommutative und assoziative Verknüpfung ist, die ein neutrales Element besitzt (der größte gemeinsame Teiler von ${}0$ und ${}0$ sei als ${}0$ festgelegt).
2. Zeige, dass das kleinste gemeinsame Vielfache eine kommutative und assoziative Verknüpfung ist, die ein neutrales Element besitzt (das kleinste gemeinsame Vielfache von ${}a$ und ${}0$ sei als ${}0$ festgelegt).
3. Zeige, dass mit diesen Verknüpfungen (mit dem GgT als Addition) ein kommutativer Halbring vorliegt.

Aufgabe * (4 Punkte)

Es sei ${}G$ eine Gruppe. Betrachte die Relation ${}\sim$ auf ${}G$, die durch

$x\sim y{\text{ genau dann, wenn }}x=y{\text{ oder }}x=y^{-1}$

erklärt ist. Zeige, dass ${}\sim$ eine Äquivalenzrelation ist.

Aufgabe * (3 (2+1) Punkte)

Es sei ${}G$ eine endliche Gruppe mit ${}n$ Elementen, wir betrachten die Verknüpfungsabbildung

$\mu \colon G\times G\longrightarrow G,\,(x,y)\longmapsto \mu (x,y)=x\circ y.$

1. Bestimme das Faseranzahltupel von ${}\mu$.
2. Sind die Verknüpfungsabbildungen zu zwei endlichen Gruppen mit der gleichen Anzahl isomorph?

Aufgabe * (3 Punkte)

Beweise den Satz über die explizite Lösung einer Matrixrekursion im diagonalisierbaren Fall.

Aufgabe * (5 (1+2+1+1) Punkte)

Es sei ${}M$ eine endliche Menge mit ${}n$ Elementen und sei  ${}k\leq n$.  Es sei  ${}V={\mathfrak {P}}_{k}\,(M)$  die Menge aller ${}k$-elementigen Teilmengen von ${}M$. Zu dieser Knotenmenge machen wir einen Graphen, indem wir zwei solche Teilmengen miteinander durch eine Kante verbinden, wenn die Teilmengen einen nichtleeren Durchschnitt besitzen.

1. Bestimme die Anzahl von ${}V$.
2. Bestimme den Grad von ${}G$ in jedem Punkt.
3. Bestimme die Anzahl der Kanten in diesem Graphen.
4. Zeige, dass der Graph regulär ist.

Aufgabe * (4 Punkte)

Zeige, dass es in einem Graphen  ${}G=(V,E)$  mit  ${}{\#\left(V\right)}\geq 2$  stets zwei Punkte gibt, deren Grad übereinstimmt.

Aufgabe * (2 Punkte)

Bestimme für einen linearen Graphen mit ${}n$ Knotenpunkten den Radius und den Durchmesser.

Aufgabe * (3 Punkte)

Beweise den Satz über Blätter an einem Baum.

Aufgabe * (2 (1+1) Punkte)

Es seien  ${}G_{1}=\left(V_{1},E_{1}\right)$  und  ${}G_{2}=\left(V_{2},E_{2}\right)$  Graphen mit der disjunkten Vereinigung  ${}G=G_{1}\uplus G_{2}$. 

1. In welcher Beziehung steht die Adjazenzmatrix ${}A$ zu ${}G$ zu den Adjazenzmatrizen ${}A_{1}$ und ${}A_{2}$ zu ${}G_{1}$ und ${}G_{2}$?
2. In welcher Beziehung steht das charakteristische Polynom zu ${}G$ zu den charakteristischen Polynomen zu ${}G_{1}$ und ${}G_{2}$?