(a) What is the maximal flow problem in a network? Explain the Ford-Fulkerson algorithm. Prove that this algorithm terminates if the initial flow is set to zero and all arc capacities are rational numbers.

(b) Let $A=\left(a_{i, j}\right)_{i, j}$ be an $n \times n$ matrix. We say that $A$ is doubly stochastic if $0 \leqslant a_{i, j} \leqslant 1$ for $i, j$ and

$$\begin{aligned} &\sum_{i=1}^{n} a_{i, j}=1 \text { for all } j \\ &\sum_{j=1}^{n} a_{i, j}=1 \text { for all } i \end{aligned}$$

We say that $A$ is a permutation matrix if $a_{i, j} \in\{0,1\}$ for all $i, j$ and

for all $j$ there exists a unique $i$ such that $a_{i, j}=1$,

for all $i$ there exists a unique $j$ such that $a_{i, j}=1$.

Let $\mathcal{C}$ be the set of all $n \times n$ doubly stochastic matrices. Show that a matrix $A$ is an extreme point of $\mathcal{C}$ if and only if $A$ is a permutation matrix.