Jedenáctá sada domácích úloh k MB103
Příklad 1. Určete maximální tok a jemu odpovídající minimální řez v následujícím
ohodnoceném orientovaném grafu:
01 01
01
0101
01 01
20
18
3
7
5 10
7
11
9
12
8
20
17
10
11
9
11
Z
S
A B
C D
E F
7
2
2
Příklad 2. Rozhodněte zda platí (řezem rozumíme množinu hran C takovou, že
po jejím odebrání z grafu neexistuje žádná cesta ze zdroje do stoku, kdykoliv však
některou z hran z C ve grafu ponecháme, nějaká taková cesta zůstane též):
a) Minimální řez v libovolné síti je právě jeden.
b) Počet řezů v síti je roven počtu orientovaných cest ze zdroje do stoku.
c) Řezů je v síti alespo tolik, co různých orientovaných cest ze zdroje do stoku.
d) Řezů v síti může být jak více tak méně než orientovaných cest ze zdroje do
stoku.
Příklad 3. Popište modifikaci Fordova­Fulkerssonova algoritmu, ve kterém budeme
zadávat kromě maximálních kapacit hran také maximální průtočnost vrcholů grafu.
1