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á 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 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
Řešení. Označíme-li hrany dle obrázku
Z
S
a
b
c d e
f
gh
i
j
pak jsou řezy následující: {f,i},{f,h,j,a},{f,j,c,a,d,e},{f,j,c,a,d,f}, {b,j,c},{b,j,h},{b,i}. 2
Příklad 2. Najděte maximální tok v síti z příkladu 1 pomocí Fordova-Fulkersonova algoritmu.
Řešení. Hodnota je 9, (f(a) = 2, f(b) = 4, f(c) = 1, f(h) = 1, f(j) = 4, f(f) = 2, f(i) = 7, jinak
nuly), není určen jednoznačně. 2
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 cest ze zdroje do stoku.
c) Řezů je v síti alespoň tolik, co různých cest ze zdroje do stoku.
d) Řezů v síti může být jak více tak méně než cest ze zdroje do stoku.
Řešení.
a) Ne. (třeba zdroj a stok jsou propojeny právě dvěma neprotínajícími se cestami se stejnou
propustností)
b) Ne. (viz graf z př. 1)
c) Ano.
d) Ne.
2