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

Homework Assignment #20.5


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 <math>G=(E,V)</math>. Without loss of generality, let <math>s</math> be the source vertex and <math>t</math> be the sink vertex in <math>V</math>. For each edge <math>(u,v)\in E</math>, let <math>c_{uv}</math> 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.

cs-312/hw20.5.1420067165.txt.gz · Last modified: 2014/12/31 23:06 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0