2012-65.md

course	course_year	question_number	tags	title	year
Optimization	IB	65	IB 2012 Optimization	Paper 4, Section II, 20H	2012

Describe the Ford-Fulkerson algorithm.

State conditions under which the algorithm is guaranteed to terminate in a finite number of steps. Explain why it does so, and show that it finds a maximum flow. [You may assume that the value of a flow never exceeds the value of any cut.]

In a football league of $n$ teams the season is partly finished. Team $i$ has already won $w_{i}$ matches. Teams $i$ and $j$ are to meet in $m_{i j}$ further matches. Thus the total number of remaining matches is $M=\sum_{i<j} m_{i j}$. Assume there will be no drawn matches. We wish to determine whether it is possible for the outcomes of the remaining matches to occur in such a way that at the end of the season the numbers of wins by the teams are $\left(x_{1}, \ldots, x_{n}\right)$.

Invent a network flow problem in which the maximum flow from source to sink equals $M$ if and only if $\left(x_{1}, \ldots, x_{n}\right)$ is a feasible vector of final wins.

Illustrate your idea by answering the question of whether or not $x=(7,5,6,6)$ is a possible profile of total end-of-season wins when $n=4, w=(1,2,3,4)$, and $M=14$ with

$$\left(m_{i j}\right)=\left(\begin{array}{cccc}

• & 2 & 2 & 2 \ 2 & - & 1 & 1 \ 2 & 1 & - & 6 \ 2 & 1 & 6 & - \end{array}\right)$$