- run the max-flow algorithm, such as Ford-Fulkerson or Edmonds-Karp, and keep the residual graph as G`.
- run DFS, from s and t, on G` and find out a reachable set R1 and R2.
- if and only if R1 + R2 = E, then return true, otherwise, return false.
For a directed graph G(V, E). We could do the following to verify the unique or not.
- run the max-flow algorithm;
- for each edge e though the min cut, increase the capacity;
- if the max flow does not change, the min cut is not unique; otherwise, it is unique.
if the max flow does not change, the min cut is unique; otherwise, it is not.
ReplyDelete这句话是不是说反了?
You are right! I have fixed that error.
DeleteThis comment has been removed by the author.
ReplyDeleteIf you run DFS from t in the residual graph then you'll reach s so R2=V (I think you should have written R1+R2=V).
ReplyDelete