Network Flow and Matching Clinic

P17. Cancellation

Use unit edges s→a,s→b,a→x,a→y,b→x,x→t,y→t. After first path s→a→x→t, give a residual augmenting path reaching value 2 and the final original-edge flow vector. Explain how to store antiparallel original edges without confusing them with residual reverse records.

P18. Capacity magnitude

State the integral Ford–Fulkerson termination argument and why it can be pseudo-polynomial. Outline the Edmonds–Karp level argument. Multiply every capacity in P17 by 10^30; explain why the algorithm need not perform 10^30 separate unit augmentations and which bit-cost qualification remains.

P19. Verify optimality

For edges s→a:3,a→t:2,s→t:1, verify optimum value 3 with a feasible per-edge flow and a matching cut. Reject the vector [3,2,1] without rerunning max flow. Explain how residual source reachability constructs a cut and why its outgoing original capacities, not both directions, define capacity.

P20. Matching and limits

For allowed pairs (0,0),(0,1),(1,0), contrast maximal and maximum matchings. Prove both directions of the unit-flow reduction. Give a Hall-deficient subset when three workers can reach only two jobs. Explain why preferences or monetary costs require a different objective.

Use Practice Solutions after preserving your independent attempt. Equivalent valid witnesses are accepted.