Sada domácích úloh k přednášce Matematika III
k odevzdání v týdnu 3. ­ 7. prosince 2006
Příklad 1. Udejte příklad sítě s alespoň dvěma různými minimálními řezy.
Příklad 2. Určete, kolik existuje homomorfismů grafů
a) z P2 do K5,
b) z K3 do K5
Příklad 3. Řez (A, B) v síti můžeme také chápat jako rozdělení množiny vrcholů V sítě do dvou
disjunktních podmnožin A a B, přičemž zdroj Z  A a stok S  B. Ukažte, že jsou-li (A, B) a
(C, D) dva různé minimální řezy v síti, tak potom i (A  C, V \ (A  C)) a (A  C, V \ (A  C))
jsou minimální řezy.