Sada domácích úloh k přednášce Matematika III
k odevzdání v týdnu 26. listopadu ­ 1. prosince 2006
Příklad 1. Řezem v síti (V, E, z, s, w) můžeme také rozumět množinu hran C  S takovou, že v
síti (V, E \ C, z, s, w) neexistuje žádná orientovaná cesta ze zdroje z do stoku (cíle, spotřebiče) s,
ale pokud z C odebereme libovolnou hranu e, tak už nová množina tuto vlastnost mít nebude,
tedy v (V, E \ C  e, z, s, w) existuje orientovaná cesta ze z do s. Určete všechny tyto řezy (a jejich
hodnoty) v následující síti:
4
5
6 2
1
2
10
Z
S
4
2
2
Příklad 2. Najděte maximální tok v síti z příkladu 1 pomocí Fordova-Fulkersonova algoritmu
(algoritmu z přednášky).
Příklad 3. Rozhodněte zda platí (při definici řezu z příkladu 1):
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.