HW 6 comments

Max 3.4
Min 0.4
Average 2.44
Median 2.6

Comments:

A. Only one got this right. Others do not realize that flow and path
are different concepts and hence do not feel necessary to show that
there are really that number of disjoint paths. By the way, the fact
that we could always obtain an integral flow when capacities are all
integral is not that obvious if we do not juse MAXFLOW algorithm.

C. Many people had trouble with proving the ``only if'' direction.
To prove this, assume v=c and then use the definition of capacity and the 
fact that  x_{uv} <= c_{uv} for all arcs (u,v) in [S,T} and 
x_{vu} >= 0 for all arcs (v,u) in [T,S]. 
Some people omit the indices in their summation, which makes the 
argument ambiguous. 
Some people tried to argue by contradiction (which is a more circuitous 
approach), but wrote down the wrong logical negation of the statement  
"x_{uv} = c_{uv} for all arcs (u,v) in [S,T} and x_{vu} = 0 for all arcs 
(v,u) in [T,S]".  This should be 
"x_{uv} NOT= c_{uv} for SOME arc (u,v) in [S,T} OR x_{vu} NOT= 0 for SOME arc
(v,u) in [T,S]".

D. In part (a), few students mess up flow and shortest path. The
weight of shortest path is added along the path, whilst the flow is
not to be added this way. Also, the correct way of writing down a
flow is to specify the value on every arc, not just some.