Homework Assignment #20.5

Show all work. i.e., justify your answers.

7.10 in the textbook

Pages 203 and 204 in the printed textbook will be useful in understanding what is required for finding the smallest (i.e., minimum capacity) $(s-t)$-cut that matches the maximum flow.

Linear Programming and the Maximum Flow Problem: Consider the directed graph $G=(E,V)$. Without loss of generality, let $s$ be the source vertex and $t$ be the sink vertex in $V$. For each edge $(u,v)\in E$, let $c_{uv}$ denote the capacity of that edge. Now, formulate the general maximum flow problem (not a specific instance) as a linear programming problem as follows:

• (a) First, define the variables. (I recommend representing the flows through each edge as your variables.)
• (b) Second, use those variables to formulate all of the necessary elements (i.e., objective function and constraints) of a linear program in algebraic terms.