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} \).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze