Ask Question
12 July, 18:42

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}.

+5
Answers (1)
  1. 12 July, 22:00
    0
    The given statement for the minimum cut (A, B) as per the new capacities is false

    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
Know the Answer?
Not Sure About the Answer?
Get an answer to your 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 ...” in 📙 Computers & Technology if there is no answer or all answers are wrong, use a search bar and try to find the answer among similar questions.
Search for Other Answers