Get Time
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Maximum Flow Tutorial: Small Doubt | Reply
In the Maximum Flow tutorial, the author quotes:
we have solved another problem that at first glance would appear to have nothing to do with maximum flow in a network, ie. given a weighted directed graph, remove a minimum-weighted set of edges in such a way that a given node is unreachable from another given node.

Unfortunately, I still can't see how the above mentioned problem gets solved while considering the Max Flow Min Cut. Can anyone please provide me a little more explanation in how this associated problem is getting solved??

Tutorial Link:
Re: Maximum Flow Tutorial: Small Doubt (response to post by Ace88Coder) | Reply
1) Our first step is converting the undirected graph into a directed graph by replacing two edges for each edge in the graph ( one forward and one backward each with a capacity of 1).
2) Our aim is to split two vertices. (i.e. there should be no path from one vertex to another if we consider one as a source and other as a tank)
3) Min cost to make a cut in the graph will be equal to min cost to separate two vertices in this graph. So if we find min-cost required for splitting all possible two vertices, and take the global minimum, we'll get the required result.
4) To make it more optimal, we can just take one vertex as source and try out for all possible sinks. This works because this vertex must be in one of the graphs after making the cut.
5) If there is an augmenting path in the residual graph, from a vertex A to another vertex B, then A and B are connected and to disconnect them we must add flow to it.
6) Once the maxFlow is reached, the vertices are disconnected which means we have made the cut necessary to split the vertices.
7) The cost of the cut is equal to the maxFlow. (Even though we make two edges for each edges at the beginning, only one of these edges would actually gets counted in our flow)