Dieser Thread soll der Diskussion der Lösungen der Klausuren zur Vorlesung Diskrete Strukturen aus dem SS08 und dem WS0809 dienen.
In diesem ersten Beitrag werden die diskutierten Lösungen laufend zusammengefasst. Ergänzungen und Korrekturen bitte als Antwort zum Thema. Einige Lösungen sind direkt zum Beitrag im Thread verlinkt, da die Forumssoftware nur 10.000 Zeichen pro Eintrag erlaubt, und sie daher nicht mehr in diesen Beitrag übernommen werden konnten.
Klausur SS08
Aufgabe 1
a)
Anzahl der Gebiete: Eulersche Polyederformel nach Anzahl der Gebiete umstellen => |Gebiete| = 2 - |V| + |E|
|V| = 8, |E| = 1/2 * Summe der Grade aller Vertizes = 16 => |Gebiete| = 10
Zeichnung eines solchen Graphen: Zuerst v8 in die Mitte von v1 bis v7 zeichnen und mit diesen verbinden. v6 mit v5, v4 und v3 sowie v7 mit v1, v2 und v3 verbinden. Abschließend v6 mit v7, v5 mit v4 und v1 mit v2 verbinden.
Eine andere Variante ist diese Zeichnung:
b)
Ist H planar?
Notwendige Bedingung für Planarität: |E| <= 3 * |V| - 6
H hat |V| = 9 und |E| = 24 (zur Berechnung siehe oben) => 24 <= 3 * 9 -6 falsche Aussage => H ist nicht planar
Ist H eulersch?
Prüfen: Graph zusammenhängend (trifft zu), alle Vertexgrade gerade (trifft zu) => H ist eulersch
Aufgabe 2
a)
gilt für
, denn es ist:
b)
Bei einer Permutation 2- Zykeln werden nur die Elemente hin- und hergetauscht:
Die erste Permutation führt also dazu das z.B. 1 und 3 vertauscht werden.
Die zweite Permutation führt dann dazu das 3 und 1 wieder zurückgetauscht werden
1- Zykel haben keinen einfluss, die Elemente bleiben an ihrer Position.
Bei n- Zykeln braucht man n Permutatioen um ein Element wieder an seine Ursprungspostion getauscht zu haben.
c)
Für Zykeltyp (2,2,2):
Für Zykeltyp (2,2,1,1):
Für Zykeltyp (2,1,1,1,1):
Für Zykeltyp (1,1,1,1,1,1): ...=1
Aufgabe 3
a)
|
Source code
|
1
2
3
4
5
|
C1 C2 C3
3--5--4--2--6 2--5--1--6--3 2--5--1--6--4
| | |
1 4 3
|
Alle Bäume haben genau 3 Blätter und gehören deswegen alle zu A.
Beispiel für T1 (Prüfer-Code: 4542):
123456
4542
1, 3 und 6 kommen nicht im Prüfer-Code vor:
12
345
6
4542
Jetzt für jede Stelle im Prüfer-Code von Links nach Rechts:
12
345
6
4542
Verbindung: 4-1
12
345
6
4542
Verbindung: 5-3
(5 Kommt nicht mehr im Prüfer-Code vor)
12
34
56
4542
Verbindung: 4-5
(4 Kommt nicht mehr im Prüfer-Code vor)
12
3456
4542
Verbindung: 2-4
(2 Kommt nicht mehr im Prüfer-Code vor)
123456
4542
Prüfer-Code abgearbeitet, die letzten verbleibenden Vertizes verbinden:
Verbindung: 2-6
b)
und
sind offensichtlich isomorph. Wie gibt man einen expliziten Isomorphismus an? Z.B. mit einer Permutation, hier also (1 4) (2 6 3) (5).
c)
Der Prüfercode hat die Länge 4 (=6Knoten-2). Dann sollen einmal deg(v2)=3, einmal deg(v3)=3, einmal deg(v4)=3 und einmal deg(v5)=3 sein. Daraus folgt jeweils, dass jeweils die Markierungen (3-1)mal vorkommen. Also für alle
. Diese werden addiert, also hierbei
.
Aufgabe 4
a)
aus
ergibt sich:
b)
Damit
im Ring
invertierbar ist, müssen 31 und 100 teilerfremd sein. Da 31 eine Primzahl ist und 100 kein Vielfaches von 31, ist dies der Fall. Wir können also mit dem erweiterten Euklidischen Algorithmus das Inverse berechnen:
|
Source code
|
1
2
3
4
5
|
100 1 0
31 0 1
7 3 1 -3
3 4 -4 13
1 2 9 -29
|
Damit ist
bzw.
das Inverse von
.
c)
kann man auch schreiben als
Dabei ist
=> 31^399 mod 100 = 71.
d)
|
Source code
|
1
2
|
p 2 3 5 7 11 13 17 19 23 29 31 37 41 ...
p-1 1 2 4 6 10 12 16 18 22 28 30 36 40 ...
|
Teiler von phi(n) = 40:
|
Source code
|
1
2
|
p-1 1 2 4 10 40
p 2 3 5 11 41
|
Die erste Zahl für m ist direkt ablesbar weil phi(p) = p - 1 ist, demnach gibt es m = 41
|
Source code
|
1
2
3
4
5
6
7
|
i phi(2^i) phi(3^i) phi(5^i) phi(11^i)
0 1 1 1 1
1 1 2 4 10
2 2 6 20 110
3 4 18
4 8
|
2 Wege:
|
Source code
|
1
2
3
4
5
6
7
|
a b c d
phi() 1 1 4 10
i 0 0 1 1
phi() 1 2 20 1
i 0 1 2 0
|
40 = phi(n) = phi(2^a)*phi(3^b)*phi(5^c)*phi(11^d)
Also:
40 = phi(5*11) = phi(55)
40 = phi(3*25) = phi(75)
40 = phi(41)
Die Zahlen für m sind 55,75 und 41
Aufgabe 5
a)
...
b)
...
c)
...
Klausur WS0809
Aufgabe 1
a)
Anzahl der Gebiete: |V| = 8, |E| = 17 => |Gebiete| = 11 (Berechnung siehe oben)
Zeichnung: Vertizes in drei Zeilen gruppieren: Erste Zeile v1 bis v3, zweite Zeile v7 und v8 sowie dritte Zeile v4 bis v6. v7 mit v1, v2, v4, v5 und v8 sowie v8 mit v2, v3, v5 und v6 verbinden. Nun v1 mit v2, v2 mit v3, v3 mit v6, v6 mit v5, v5 mit v4 und v4 mit v1 verbinden. Abschließend v1 mit v3 sowie v6 mit v4 verbinden.
Eine andere Variante ist diese Zeichnung:
Hat G einen Euler-Weg?
Prüfen: Graph zusammenhängend (trifft zu), zwei Vertexgrade ungerade (trifft zu) => G hat einen Euler-Weg
b)
Ist H planar?
H hat |V| = 9 und |E| = 23 => 23 <= 3 * 9 -6 falsche Aussage => H ist nicht planar (Berechnung siehe oben)
Ist H eulersch?
Prüfen: Graph zusammenhängend (trifft zu), alle Vertexgrade gerade (trifft nicht zu) => H ist nicht eulersch
Aufgabe 2
a)
Die Ordnung ist die Anzahl der Hintereinanderausführung einer Permutation, bis die Identität erreicht wird. Einfach berechnen lässt sie sich durch den kgV des Zykeltyps.
hat die Ordnung
,
die Ordnung
. Somit
.
b) + c)
Damit eine Permutation die Ordnung 6 hat, muss das kgV des Zykeltyps 6 sein. Bei einer 6-elementigen Permutation kommen nur die Typen (3, 2, 1) und (6) in Frage. Damit gibt es
Möglichkeiten.
Aufgabe 3
a)
aus
ergibt sich:
b)
Damit
im Ring
invertierbar ist, müssen 77 und 108 teilerfremd sein. Wir wenden den erweiterten Euklidischen Algorithmus an um zu prüfen, ob der
ist und um dann das Inverse zu berechnen:
|
Source code
|
1
2
3
4
5
|
108 1 0
77 0 1
31 1 1 -1
15 2 -2 3
1 2 5 -7
|
Damit ist
das Inverse von
.[/quote]
c)
d)
...
Aufgabe 4
a) + b)
T1: Verbindungen: 1-4;2-5;3-5;4-6;5-6
T2: Verbindungen: 1-2;3-6;5-4;2-4;2-6
T3: Verbindungen: 1-2;3-5;4-2;2-5;5-6
c)
ausführliche Lösung
Aufgabe 5
a)
...
b)
...
c)
...
Zusätzliches
Rekursionsformeln mit konstanten Koeffizienten p und q