a
2
8
10
d
5
7
5
s
2
b
t
8
2
9
e
1
1
c
S = (D, c) jest siecią. PrzepustowoS
ć każdego łuku wynosi 20. Liczby przy łukach oznaczają wartoS
ci funkcji f,
definiującej przepływ w tej sieci.
(1) Wykaż, że f spełnia warunki przepływu. Oblicz wartoS
ć tego przepływu.
(2) Wyznacz przekrój odpowiadający zbiorowi wierzchołków U = {a, b} i oblicz przepustowoS
ć tego przekroju
oraz przepływ przez ten przekrój.
(3) Ile jest wszystkich przekrojów tej sieci, odpowiadających takim zbiorom wierzchołków U, w których s U
i t U ?
(4) WS
ród przekrojów spełniających warunek z pktu (3) spróbuj wyznaczyć przekrój minimalny.
(5) Wskaż jakąS
S
cieżkę powiększającą ze x
ródła s do ujS
cia t i powiększ wartoS
ć przepływu f z s do t.
(6) Ile wynosi maksymalna wartoS
ć przepływu w tej sieci?
a
a
a
d
d
d
s
s
b
t
b s
t
b
t
e
e
e
c
c
c
a
a
a
d
d
d
s
s
b
t s
b
t
b
t
e
e
e
c
c
c
___________________________________________________________________________
x
x
x
s
y
s
t y
s
t y
t
v
v
v
x
x
x
s
y
s
y
t
s
t y
t
v
v
v