Considering the max-flow and min-cut problems in a flow network G, let (A*, B*) be the...

Transcribed Image Text:

Considering the max-flow and min-cut problems in a flow network G, let (A*, B*) be the minimal s - t cut that is obtained from Ford-Fulkerson algorithm. Denote c* C(A*, B*). = (a) [5pts.] prove that the following statements are equivalent. + (A*, B*) is the not the unique minimal s - t cut. + There exists an edge e = (x, y), x ≤ A*, y ≤ B* such that if c(e) is increased by one, in the resulting graph G', the min-cut value in G' is still the same as c*. (b) [5pts.] Write an algorithm to determine if G has a unique minimal s-t cut. Provide proofs on the correctness and the running time. Considering the max-flow and min-cut problems in a flow network G, let (A*, B*) be the minimal s - t cut that is obtained from Ford-Fulkerson algorithm. Denote c* C(A*, B*). = (a) [5pts.] prove that the following statements are equivalent. + (A*, B*) is the not the unique minimal s - t cut. + There exists an edge e = (x, y), x ≤ A*, y ≤ B* such that if c(e) is increased by one, in the resulting graph G', the min-cut value in G' is still the same as c*. (b) [5pts.] Write an algorithm to determine if G has a unique minimal s-t cut. Provide proofs on the correctness and the running time.

Answer rating: 100% (QA)

a Equivalence of Statements A B is not the unique minimal st cut There exists an edge e x y x A y B such that if ce is increased by one in the resulti... View the full answer