Tok v mřížce
Úloha číslo: 3833
Nechť \(G=(V,E)\) je síť tvaru mřížky \(5 \times 5\), t.j. \[\begin{eqnarray*} V & = & \{1{,}2,3{,}4,5\} \times \{1{,}2,3{,}4,5\} \\ E & = & \{((x,y),(x+1,y)), 1\leq x \leq 4, 1 \leq y \leq 5\} \cup \\ & & \{((x,y),(x,y+1)), 1\leq x \leq 5, 1 \leq y \leq 4\} \ , \end{eqnarray*}\] s kapacitami \(c(((x,y),(x',y'))) = 1/ \min\{x+y-1, 10-x-y\}\).
Určete maximální tok ze zdroje \((1{,}1)\) do spotřebiče \((5{,}5)\).
Odpověď
Maximální tok v této síti je \(\frac{5}{3} \).