17.9.2004

Vordiplomsklausur Diskrete Strukturen, SS 2004

Prof. Dr. U. Schoenwaelder

Tragen Sie bitte auf diesem Deckblatt leserlich und in Blockbuchstaben Ihren Namen und Ihre Matrikelnummer ein und unterschreiben Sie.

Name:

Vorname:

Matrikelnummer:

Eigenhändige Unterschrift:

Krz  Erg  7  8  9  10  Σ

Punkte

Nachk.

Zum Ankreuzteil:

Kreuzen Sie bei jeder Frage entweder ”Ja“ oder ”Nein“ oder nichts an. Auswertung: Jedes richtige Kreuz gibt einen Pluspunkt, jedes falsche Kreuz einen Minuspunkt. Jede Aufgabe gibt immer mindestens 0 Punkte, Minuspunkte wirken also nicht über Aufgaben hinweg. Wenn Sie bei einer Frage unsicher sind, machen Sie einfach kein Kreuz. Sie brauchen Ihre Kreuze nicht zu begründen!

Zum Ergebnisteil:

In diesem Teil müssen Sie Ihre Aussagen nicht begründen. Es zählt nur das richtige Ergebnis.

Zu den Aufgaben mit Begründungen:

In diesem Teil müssen Sie alle Aussagen begründen. Natürlich brauchen Sie Aussagen aus der Vorlesung nicht noch einmal zu beweisen.

Vordiplomsklausur, 17.9.2004

Diskrete Strukturen, SS 2004, Prof. Dr. U. Schoenwaelder

Name: Matrikelnummer:

Kreuzen Sie bei jeder Frage entweder ”Ja“ oder ”Nein“ oder nichts an. Auswertung der Multiple-Choice-Aufgaben: Ein richtiges Kreuz ergibt +1 Punkt, ein falsches Kreuz ergibt −1 Punkt, keine Angabe zählt 0 Punkte. In jeder Aufgabe bekommen Sie mindestens 0 Punkte.

1 Welche der folgenden Aussagen sind richtig?

In einem Graph mit einer Eulertour kommen nur Ecken mit geradem Grad vor.

□ Ja □ Nein

Ein hamiltonscher Graph kann mehr als eine Zusammenhangskomponente haben.

□ Ja □ Nein

Jeder vollständige Graph ist hamiltonsch.

□ Ja □ Nein

Jeder endliche Graph hat einen endlichen Durchmesser.

□ Ja □ Nein

2 Welche der folgenden Aussagen sind richtig?

Jeder zusammenhängende Graph enthält einen eindeutig bestimmten Spannbaum als Teilgraph.

□ Ja □ Nein

Jeder Baum ist zusammenhängend.

□ Ja □ Nein

Alle zusammenhängenden schlichten Graphen haben die gleiche Zusammenhangszahl.

□ Ja □ Nein

Beliebige zwei Bäume mit gleicher Eckenzahl sind zueinander isomorph.

□ Ja □ Nein

Bearbeiten Sie die folgenden Rechenaufgaben und schreiben Sie die Ergebnisse in die dafür vorgesehenen Kästchen. Sie brauchen Ihre Ergebnisse nicht zu begründen, für Begründungen und Ansätze gibt es aber auch keine Punkte. Für die richtige Antwort bekommen Sie die angegebene Punktzahl. Für eine falsche Antwort gibt es null Punkte.

3 Es sei G = (V, E, f) der folgende Graph: (Jeweils 2 Punkte)

Wie viele Elemente hat die Automorphismengruppe von G?

Wie viele Färbungen der Ecken mit 2 Farben hat G?

Wie viele Muster bezüglich der Automorphismengruppe von G ergeben diese Färbungen?

4 Bestimmen Sie die folgenden Anzahlen. (Jeweils 1 Punkt)

Die Anzahl der 3-elementigen Teilmengen einer 5-elementigen Menge ist

Die Anzahl der Permutationen von {1, 2, 3, 4, 5, 6}, welche 2 und 4 vertauschen, ist

Die Anzahl der Zahlpartitionen von 4 ist

Die Anzahl der Abbildungen f : {1, 2, 3, 4} → {1, 2, 3} ist

Die Anzahl der surjektiven Abbildungen f : {1, 2, 3, 4, 5} → {2, 3, 4, 5, 6} ist

Die Anzahl der Teilmengen der Gruppe S_{{1,2,3}} ist Name: Matrikelnummer:

5 Es seien die Permutationen σ := ( \begin{matrix}1 2 3 4 5 6 7 8 9 \\ 9 6 8 3 2 7 5 1 4 \end{matrix} ) sowie τ := (2 8)(3 6 1 4 7 5)

aus S_{{1,2,3,4,5,6,7,8,9}} gegeben. (Jeweils 1 Punkt)

Die Zykeldarstellung von σ ist

Die Ordnung von τ ist

Die Zykeldarstellung von τ^{−1} ist

Die Zykeldarstellung von τ^{105} ist

Die Zykeldarstellung von σ^{−1} · τ · σ ist

6 Bestimmen Sie die folgenden Zahlen. (Jeweils 3 Punkte)

Das multiplikative Inverse von 17 im Körper \underline{101} = \{0, 1, …, 100\} ist

Bei der Lösung (x, y) ∈ ℤ × ℤ von 1 = 101 · x + 42 · y mit 50 ≤ x ≤ 100 ist x gleich

Beantworten Sie die folgenden Aufgaben schriftlich. Beweisen Sie alle Ihre Behauptungen. Schreiben Sie auf jedes Blatt Ihren Namen und Ihre Matrikelnummer. Fangen Sie jede Aufgabe auf einer neuen Seite an.

7 Bestimmen Sie die Anzahl der natürlichen Zahlen aus {1, 2, …, 10000} die durch 2, 3 oder 5 teilbar sind, also die Anzahl der Elemente in der Menge

{n ∈ ℕ | 1 ≤ n ≤ 10000 und (2|n oder 3|n oder 5|n)} . (4 Punkte)

8 Bestimmen Sie alle ungeraden, natürlichen Zahlen n mit φ(n) = 6, wobei φ die Eulersche Phi-Funktion ist. (4 Punkte)

9 Es sei G := S_{{1,2,3,4,5}} die symmetrische Gruppe, die die fünf Zahlen {1, 2, 3, 4, 5} permutiert. Die Menge M := Ω × Ω × Ω aller Tripel (a, b, c) mit a, b, c ∈ Ω ist eine G-Menge, wenn man für g ∈ G

(a, b, c) ∗ g := (a^{g}, b^{g}, c^{g})

festlegt. Geben Sie die verschiedenen G-Bahnen von M an. Bestimmen Sie die jeweilige Bahnlänge. Wie viele Elemente hat der Stabilisator von (1, 1, 2)? (5 Punkte)

10 (a) Definieren Sie den Begriff ”Kreis in einem Graphen“. (2 Punkte)

(b) Es sei G = (V, E, f) ein Baum. Zeigen Sie, dass es für je zwei Ecken v, w ∈ V genau einen Weg von v nach w gibt. (4 Punkte)