2015-63.md

course	course_year	question_number	tags	title	year
Optimization	IB	63	IB 2015 Optimization	Paper 1, Section I, H	2015

(a) Consider a network with vertices in $V={1, \ldots, n}$ and directed edges $(i, j)$ in $E \subseteq V \times V$. Suppose that 1 is the source and $n$ is the sink. Let $C_{i j}, 0<C_{i j}<\infty$, be the capacity of the edge from vertex $i$ to vertex $j$ for $(i, j) \in E$. Let a cut be a partition of $V={1, \ldots, n}$ into $S$ and $V \backslash S$ with $1 \in S$ and $n \in V \backslash S$. Define the capacity of the cut $S$. Write down the maximum flow problem. Prove that the maximum flow is bounded above by the minimum cut capacity.

(b) Find the maximum flow from the source to the sink in the network below, where the directions and capacities of the edges are shown. Explain your reasoning.