Define the optimal distribution problem. State what it means for a circuit $P$ to be flow-augmenting, and what it means for $P$ to be unbalanced. State the optimality theorem for flows. Describe the simplex-on-a-graph algorithm, giving a brief justification of its stopping rules.

Consider the problem of finding, in the network shown below, a minimum-cost flow from $s$ to $t$ of value 2 . Here the circled numbers are the upper arc capacities, the lower arc capacities all being zero, and the uncircled numbers are costs. Apply the simplex-on-agraph algorithm to solve this problem, taking as initial flow the superposition of a unit flow along the path $s,(s, a), a,(a, t), t$ and a unit flow along the path $s,(s, a), a,(a, b), b,(b, t), t$.

Part II 2003