HW 6 comments


I recommend everyone look at the solutions.  

Many people had difficulty explaining their answers thoroughly in A.

Most people understood B. 
On B, part b, there is a slight error in the solution.  
After the flow augmentation, the new flow has value of 5 (not 4), so the 
rightmost figure should have 5 units of flow into a and out of z.  
Also, the flow on arc (a,b) should be 3 instead of 2.  

For C, most people (who did this problem) have more or less
the right idea, though some students are a bit vague/sloppy with their
argument (e.g., do not explicitly make use of the capacity bounds
0 <= x_{uv} <= c_{uv}  in their argument).

Many people understood D.  They need to be specific about why the maximum flow is not unique by explicity
writing down two distinct flows.  For D, part c, they need to write down two distinct min cuts.  For
D part d, they need to pay attention to the direction of the arc... (a,b) and (b,a) have different
meaning since the arcs are directional.  

Very few people tried the bonus.