This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-312:hw20.5 [2014/12/31 16:22] ringger |
cs-312:hw20.5 [2015/03/07 17:52] (current) ringger [Question 2] |
||
---|---|---|---|

Line 7: | Line 7: | ||

7.10 in the textbook | 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. | + | 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 === | === 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: | 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. | + | * (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 of a linear program in algebraic terms, and make sure that your formulation is in standard form up to step #1. | + | * (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. |