JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search My Post History  |  My Watches  |  User Settings Forums Tutorial Discussions Maximum Flow tutorial Re: Finding Minimum Edges Minimum Cut Revision History (3 edits)
 Re: Finding Minimum Edges Minimum Cut (response to post by mogers) (some explanations related to the first post are in edit) Did you even read my post ? :) Yes.It doesn't work if we want the minimum set of edges with smallest index.Well, do we need it? :) I mean, is there any more or less practical problem that asks it?Here is a tough case: Source and Sink are both connected to a complete graph K_n, all egdes have the same capacity.Consider any decomposition of the vertices of K_n into sets of != 2 vertices. Take any set S with |S| >= 3 and form a cycle with its vertices. In the 'obvious' minimum cut there are only edges (Source, v) and (v, Sink) but it is clear that with such cycle formed you can take any(but only one at a time) vertice v from it and change the edge (Source, v) to (v, next[v]). This minimum cut will contain the same number of edges and you can play this trick with any vertice in any set of any decomposition. The number of such 'min cuts' can be calculated, but even now we can say it's large enough.
 Re: Finding Minimum Edges Minimum Cut (response to post by mogers) Did you even read my post ? :) Yes. It is vague enough to be misunderstood.``` edge 2 edge 1 Source -------> A -------> Sink ```This cannot be a correct example of a residual network because Sink can be reached from Source.Consider three possible options:1. capacity(edge 1) > capacity(edge 2) = XHere we can push X units of flow from Source to Sink which leads to``` edge 2 edge 1 Source <------- A <-------> Sink ```2. capacity(edge 1) < capacity(edge 2), which in the same way leads to``` edge 2 edge 1 Source <-------> A <------- Sink ```In both cases dfs yields the correct answer3. capacity(edge 1) = capacity(edge 2)Here only two but not three edges(unlike above) are left in the residual network:``` edge 2 edge 1 Source <------- A <------- Sink ```Here what we need is a matter of definitions. In fact, dfs works right if you want any minimum cut.It doesn't work if we want the minimum set of edges with smallest index.Oh, now I get what you wanted to say.Well, do we need it? :) I mean, is there any more or less practical problem that asks it?After thinking more about it, I have no idea of how to do it :)Here is a tough case: Source and Sink are both connected to a complete graph K_n(which has only edges of capacity n) with egdes of capacity 1. Depending on how you push the flow, you can form a lot(if not all) of subsets of edges which will form a cut.edit: some new thoughts
 Re: Finding Minimum Edges Minimum Cut (response to post by mogers) Did you even read my post ? :) Yes. It is vague enough to be misunderstood.``` edge 2 edge 1 Source -------> A -------> Sink ```This cannot be a correct example of a residual network because Sink can be reached from Source.Consider three possible options:1. capacity(edge 1) > capacity(edge 2) = XHere we can push X units of flow from Source to Sink which leads to``` edge 2 edge 1 Source <------- A <-------> Sink ```2. capacity(edge 1) < capacity(edge 2), which in the same way leads to``` edge 2 edge 1 Source <-------> A <------- Sink ```In both cases dfs yields the correct answer3. capacity(edge 1) = capacity(edge 2)Here only two but not three edges(unlike above) are left in the residual network:``` edge 2 edge 1 Source <------- A <------- Sink ```Here what we need is a matter of definitions. In fact, dfs works right if you want any minimum cut.It doesn't work if we want the minimum set of edges with smallest index.Oh, now I get what you wanted to say.Well, do we need it? :) I mean, is there any more or less practical problem that asks it? Even if there is(which would be strange) I think that a slightly improved dfs still would do. The example above can be solved by looking one vertice forward. Maybe it works in general case, I'm not quite sure.edit: nothing special
 Re: Finding Minimum Edges Minimum Cut (response to post by mogers) Did you even read my post ? :) Yes.``` edge 2 edge 1 Source -------> A -------> Sink ```This cannot be a correct example of a residual network because Sink can be reached from Source.Consider three possible options:1. capacity(edge 1) > capacity(edge 2) = XHere we can push X units of flow from Source to Sink which leads to``` edge 2 edge 1 Source <------- A <-------> Sink ```2. capacity(edge 1) < capacity(edge 2), which in the same way leads to``` edge 2 edge 1 Source <-------> A <------- Sink ```3. capacity(edge 1) = capacity(edge 2)Here only two but not three edges(unlike above) are left in the residual network:``` edge 2 edge 1 Source <------- A <------- Sink ```In all these cases dfs yields the correct answer.