Úkoly z Kombinatoriky a grafů, 9. série

Veškerá tvrzení precizně zdůvodněte.

(9.1) Nechť G je síť, f tok na ní a A, B ⊆ V (G) dvě množiny vrcholů takové, že z ∈ A, B a s ∈ V \ A, V \ B. Definujme

f(A, V \ A) = ∑_{(u,v)∈E(G),u∈A,v∈V \A} f(u, v) − ∑_{(v,u)∈E(G),u∈A,v∈V \A} f(v, u)

a analogicky f(B, V \ B). Dokažte, že pro libovolnou volbu A a B platí

f(A, V \ A) = f(B, V \ B) = w(f).

4 body

(9.2) Nechť G je síť. Dokažte, že pro libovolnou volbu toku f na G a R řezu G

platí

w(f) ≤ c(R).

4 body