##### Differences

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

 cs-312:hw20.5 [2014/12/31 23:06]ringger created cs-312:hw20.5 [2015/03/08 00:52] (current)ringger [Question 2] 2015/03/08 00:52 ringger [Question 2] 2015/03/06 23:40 ringger [Question 2] 2015/03/06 19:38 ringger [Question 2] 2015/03/06 19:37 ringger 2014/12/31 23:22 ringger 2014/12/31 23:06 ringger created Next revision Previous revision 2015/03/08 00:52 ringger [Question 2] 2015/03/06 23:40 ringger [Question 2] 2015/03/06 19:38 ringger [Question 2] 2015/03/06 19:37 ringger 2014/12/31 23:22 ringger 2014/12/31 23:06 ringger created 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 <​math>​G=(E,V)​.  Without loss of generality, let <​math>​s ​be the source vertex and <​math>​t ​be the sink vertex in <​math>​V​. For each edge <​math>​(u,v)\in E​, let <​math>​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. 