Network flow in a grid
Task number: 3977
Let \(G=(V,E)\) be a grid network \(5 \times 5\), i.e. \[\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*}\] with capacities \(c(((x,y),(x’,y’))) = 1/ \min\{x+y-1, 10-x-y\}\).
Determine the maximum flow from the source \((1{,}1)\) to the target \((5{,}5)\).
Answer
The maximum flow in this network is \(\frac{5}{3}\).
