Hilfe zur Klausuraufgabe Klausur Sep 2016 (SS 2016)

Hallo zusammen,

hier meine Ergebnisse.

Aufgabe 1:
a)
Spaltenweise von links nach rechts:
6 4 3 9 2 1
5 7 8 10

b)
i)
[10, 9, 2, 1, 9]

ii)
[10, 9, 1, 2, 3]

iii)
[4, 7, 8, 3, 4]

c)
Nein, denn G enthält Kreise mit ungerader Kantenzahl (z. B. [ 9, 2, 1]).

d)
11000000000000
10110000000000
00101110000000
00001001100000
00000000010000
00000001011000
00000000101100
00000100000110
01010010000011
00000000000001

e)
B(G)*BT(G) = A(G) - Delta,
wobei A(G) die Adjazenzmatrix ist und Delta eine Diagonalmatrix, welche zu jedem Knoten die Anzahl der Kanten anzeigt. Somit ist offensichtlich die Anzahl der Kanten bekannt und zudem ist direkt ablesbar welcher Knoten zu welchem Knoten eine direkte Verbindung hat.

Aufgabe 2:
Delta (1) = 2 CD (1) = 0,2 (Periode)
Delta (2) = 3 CD (2) = 0,3 (Periode)
Delta (3) = 4 CD (3) = 0,4 (Periode)
Delta (4) = 3 CD (4) = 0,3 (Periode)
Delta (5) = 1 CD (5) = 0,1 (Periode)
Delta (6) = 3 CD (6) = 0,3 (Periode)
Delta (7) = 3 CD (7) = 0,3 (Periode)
Delta (8) = 3 CD (8) = 0,3 (Periode)
Delta (9) = 5 CD (9) = 0,5 (Periode)
Delta (10) = 1 CD (10) = 0,1 (Periode)
Maximum ist CD (9) = 0,5 (Periode).

Aufgabe 3:
a)
D(10) = (
0123543212
1012433212
2101322112
3210211223
5432012345
4321101234
3321210123
2212321012
1112432101
2223543210)

b)
CC (1) = 9/23 ~= 0,39
CC (2) = 9/19 ~= 0,47
CC (3) = 9/15 = 0,6 <-- Maximum
CC (4) = 9/17 ~= 0,53
CC (5) = 9/29 ~= 0,31
CC (6) = 9/21 ~= 0,43
CC (7) = 9/18 = 0,5
CC (8) = 9/16 ~= 0,56
CC (9) = 9/16 ~= 0,56
CC (10) = 9/24 ~= 0,38

Aufgabe 4:
a)
23320
12210
01100
00001
23310

b)
Ich habe ein Schema mehr benötigt als vorgedruckt war, das ist also offensichtlich nicht die optimale Lösung.

Schema 1:
23320 3 (-)
12210 3 (-)
01100 3
00001 1
23310 1 (6)

01001
(1)
Eta = 1

Schema 2:
12210 3 (-)
01100 3 (-)
01101 3
00002 1
12200 1

01001
(2)
Durchbruch!

Schema 3:
12210 4 (-)
01100 4 (5)
01101 4 (1)
00002 1
12200 2 (6)

10012
(2) (6)(1)
Eta = 1

Schema 4:
11110 4 (-)
00000 4 (5)
00001 4
10013 1
11100 2 (6)

11012
(6)(1)
Durchbruch!

Schema 5:
11110 4
00000 4
00001 4
10013 1
11100 2

11012

Aufgabe 5:
a)
Zielfunktion f = |Ei|
Es bezeichne |Ei| die Anzahl der Kanten mit Endknoten in V1 und V2.
min Summenzeicheni |Ei|

b)
i)
Ja, mit V1 = ( 2, 3, 4, 6, 10) und V2 = ( 1, 5, 7, 8, 9) existieren zwei gleich große disjunkte Knotenmengen.

ii)
Nein, da hier in V1 7 Elemente sind und somit keine gleich großen disjunkten Mengen existieren.

c)
0111010001 1011010001 8 9 1 10 0,1 nein
1011010001 1101010001 9 8 -1 5 ja
1101010001 1110010001 8 9 1 2,5 0,4 nein
1110010001 1111000001 9 7 -2 1,25 ja
1111000001 1111100000 7 7 0 5/8 0 nein
1111100000 0111110000 7 6 -1 5/16 ja