2.8.2004

Scheinklausur 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.

Scheinklausur, 2.8.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?

Jeder hamiltonsche Graph ist zusammenhängend.

□ Ja □ Nein

Jeder hamiltonsche Graph besitzt eine Eulertour.

□ Ja □ Nein

Jeder hamiltonsche Graph besitzt genau einen Hamiltonkreis oder Hamiltonweg.

□ Ja □ Nein

Jeder Graph, der eine Eulertour besitzt, ist zusammenhängend.

□ Ja □ Nein

2 Welche der folgenden Aussagen sind richtig?

Jeder Graph enthält einen Spannbaum als Teilgraph.

□ Ja □ Nein

Jeder Baum enthält eine Brücke.

□ Ja □ Nein

Ein endlicher Graph G ist ein Wald genau dann, wenn jede Kante von G eine Brücke ist.

□ Ja □ Nein

Alle Wälder haben die gleiche Zusammenhangszahl.

□ 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 Bestimmen Sie die folgenden Anzahlen. Dabei ist bis auf Isomorphie zu zählen, d.h. zueinander

isomorphe Graphen zählen nur einmal. (Jeweils 2 Punkte)

Die Anzahl schlichter Graphen mit 3 Ecken ist

4

Die Anzahl schlichter Graphen mit 5 Ecken und 3 Kanten ist

4

Die Anzahl zusammenhängender Graphen mit 4 Ecken und 3 Kanten ist

2

Die Anzahl von Graphen mit 10 Ecken und 2 Kanten ist

7

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

Die Anzahl der Permutationen von {1, 2, 3, 4, 5} ist

120

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

20

Die Anzahl der Partitionen einer 4-elementigen Menge ist

15

Die Anzahl der Teilmengen einer 5-elementigen Menge ist

32

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

360

Die Anzahl der surjektiven Abbildungen f : {1, 2, 3, 4} → {1, 2} ist 14 Name: Matrikelnummer:

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

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

Die Zykeldarstellung von σ ist

(1 5 2 7 4)(3 9)(6 8)

Die Ordnung von τ ist

12

Die Zykeldarstellung von (τ^{−1})^{2} ist

(1 7 3)(2 4)(5 6)

Die Zykeldarstellung von τ^{98} ist

(1 3 7)(2 4)(5 6)

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

(5 4 9)(7 8 1 2)

6 Berechnen Sie einen größten gemeinsamen Teiler d von 612 und 572, wobei d > 0 gelten soll. Bestimmen Sie dann x, y ∈ ℤ, so daß d = x · 612 + y · 572 mit 0 ≤ x < \frac{572}{d} gilt. (Jeweils 2 P.)

Die Lösung für d ist

4

Die Lösung für x ist

43

Die Lösung für y ist

−46

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 Es seien m, n ∈ ℕ mit m | n (das heißt m teilt n in ℤ). (4 Punkte)

Zeigen Sie, dass dann auch φ(m) | φ(n) gilt. Hier ist φ die Eulersche Phi-Funktion.

8 Es sei G = S_{Ω} die symmetrische Gruppe auf der Menge Ω = {1, 2, 3, 4, 5, 6, 7}. Die Menge M = {{a, b} | a, b ∈ Ω, a ≠ b} der zweielementigen Teilmengen von Ω ist eine G-Menge, wenn man für g ∈ G

{a, b} ∗ g := {a^{g}, b^{g}}

festlegt. Bestimmen Sie die Länge der Bahn {3, 7} ∗ G und die Ordnung des Stabilisators G_{{3,7}}.

(4 Punkte)

9 Zehn befreundete Radrennfahrer nehmen an einem Radrennen teil und fahren immer hintereinander. Jeden Kilometer wechseln sie ihre Reihenfolge wie folgt (siehe auch folgende Abbildung):

• Der erste Fahrer wird der letzte,

• der zweite Fahrer der vorletzte,

• der dritte Fahrer der drittletzte und

• alle anderen Fahrer wechseln um 3 Positionen nach vorne.

A B C D E F G H I K → D E F G H I K C B A

(a) Nach wievielen Wechseln fährt Fahrer A erstmals wieder ganz vorne?

(b) Nach wievielen Wechseln fahren alle erstmals wieder in der Reihenfolge wie am Anfang? (2 + 2 Punkte)

10 Es sei n ∈ ℕ mit n ≥ 3 und G = (V, E, f) ein schlichter Graph mit |V | = n und |E| > \binom{n−1}{2}. (a) Zeigen Sie, dass G zusammenhängend ist. (b) Gibt es einen unzusammenhängenden, schlichten Graphen G mit |V | = n und |E| = \binom{n−1}{2}? (3 + 2 Punkte)