Message No. 153
Moed B: Common errors at question 2 (to be updated)
Q.2c:

Some students stated that the constructed network has no finite cut, except for that isolating s and that isolating t. Some other students stated that the min-cut should isolate s.

A counter-example to both statements is the network with the following edges: (s,u1) and (v2,t) of capacity 1, (s,u2) and (v1,t) of capacity 2, (u1,v1) and (u2,v2) of capacity infinity. The cut ({s,u2,v2}, {u1,v1,t}) is finite and minimum, with capacity 2.

published on 09/08/2016 14:32:28 by Yefim Dinitz