Question

Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. Let G be an arbitrary flow network with a source s, a sink t, and a positive integer capacity ce on every edge e. Let (A, B) be a mimimum s-t cut with respect to these capacities {ce : e ? E}. Now, suppose we add 1 to every capacity; then, (A, B) will still be a minimum s-t cut with respect to these new capacities {1+ ce : e ? E}.

Answer 1

The given statement for the minimum cut (A, B) as per the new capacities is false

Step-by-step explanation:

Assume a graph whose vertices are s, v1, v2, v3, m, t.

The edges for each i would be (s, vi) and (vi, m).

Also, there is as edge (m, t).

The capacity for the all the edges is 1 except the edge (m, t).

The capacity of the edge (m, t) is 4.

Now set A and B as follows:

A = {s}

B = V – A.

This will result the minimum cut of capacity 3.

But if one is added to the capacity of each edge, then the above cut will result with the capacity of 6.

This 6 is larger than the capacity of 4 which is obtained by the following:

B = {t}

A = V – B.

Thus, the given statement for the minimum cut (A, B) as per the new capacities is false