Aufgabe 1:
a) F (schwacher Zusammenhang ist notwendige, aber keine hinreichende Bed. für gerichtetes Gerüst, vgl. S. 20)
b) W
c) F (vollständige Digraphen sind nie bipartit)
d) W
e) W [S(1,3) und R(2,5,4)]
Aufgabe 2:
a)
Anfangsflussstärke = 7
1. Fluss: 1-4-7-8 mit +5
2. Fluss: 1-2-6-8 mit +1
b) Kapazität = 13
min. (1,8)-Schnitt = C<A,B> mit A = { 1,2,3,4} und B = { 5,6,7,8}
my(C<A,B>) = 13
Aufgabe 3:
a)
Standort B beliefert A und B
Standort D beliefert C,D,E
b) und der Rest folgt noch
a) F (schwacher Zusammenhang ist notwendige, aber keine hinreichende Bed. für gerichtetes Gerüst, vgl. S. 20)
b) W
c) F (vollständige Digraphen sind nie bipartit)
d) W
e) W [S(1,3) und R(2,5,4)]
Aufgabe 2:
a)
Anfangsflussstärke = 7
1. Fluss: 1-4-7-8 mit +5
2. Fluss: 1-2-6-8 mit +1
b) Kapazität = 13
min. (1,8)-Schnitt = C<A,B> mit A = { 1,2,3,4} und B = { 5,6,7,8}
my(C<A,B>) = 13
Aufgabe 3:
a)
Standort B beliefert A und B
Standort D beliefert C,D,E
b) und der Rest folgt noch