**This is an old revision of the document!**

# Homework Assignment #20.5

## Exercises

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

### Question 1

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.

TODO: add pages for online textbook.

### Question 2

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.
(b) Second, use those variables to formulate all of the necessary elements of a linear program in algebraic terms, and make sure that your formulation is in standard form up to step #1.

Back to top