| course |
course_year |
question_number |
tags |
title |
year |
Optimization |
IB |
72 |
|
$2 . \mathrm{I} . 9 \mathrm{C} \quad$ |
2006 |
Consider the maximal flow problem on a finite set $N$, with source $A$, sink $B$ and capacity constraints $c_{i j}$ for $i, j \in N$. Explain what is meant by a cut and by the capacity of a cut.
Show that the maximal flow value cannot exceed the minimal cut capacity.
Take $N={0,1,2,3,4}^{2}$ and suppose that, for $i=\left(i_{1}, i_{2}\right)$ and $j=\left(j_{1}, j_{2}\right)$,
$$c_{i j}=\max \left{\left|i_{1}-i_{2}\right|,\left|j_{1}-j_{2}\right|\right} \quad \text { if } \quad\left|i_{1}-j_{1}\right|+\left|i_{2}-j_{2}\right|=1,$$
and $c_{i j}=0$ otherwise. Thus the node set is a square grid of 25 points, with positive flow capacity only between nearest neighbours, and where the capacity of an edge in the grid equals the larger of the distances of its two endpoints from the diagonal. Find a maximal flow from $(0,3)$ to $(3,0)$. Justify your answer.