Jedenáctá sada domácích úloh k přednášce Matematika III
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:
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) Počet řezů v síti je roven počtu orientovaných cest ze zdroje do stoku.
b) Počet maximálních toků v síti je roven počtu minimálních řezů.
c) Řezů v síti může být jak více tak méně než orientovaných cest ze zdroje do stoku.