Removing minimum no of edges to disconnect two vertices in a graph
Here I am trying to disconnect two vertices in a graph with minimum edge removal possible.
In this graph between two vertices A and Z you can find the answer in many ways. In optimal way you can remove just one edge from A to B .
If there is any specific algorithm for this?
I found some suggestions to solve this by using maximum flow min cut problem but I am not getting general idea to convert this problem into max flow min cut theorem. Also in the process I might end up removing an edge between F and G which is useless.
This can be solved using Max Flow - Min Cut problem.
You can model your graph into network flow as follows:
1. Consider A to be the source vertex, Z to be the sink vertex.
2. Set the capacity of each edge to be 1 unit.
Now, solve the Max Flow - Min Cut problem in above network. With it you will be able to find number of edge-disjoint paths from A to Z . For every such path, remove the first edge (edge originating from source A ).
Proof :
Observe that after removing above edges, you won't be able to reach A to Z . If you had a path, then Max flow algorithm would have included this path in set of edge-disjoint-paths.
Also, by construction of network, you can't remove lesser number of edges to disconnect A from Z
上一篇: 图解算法
下一篇: 删除最少的边数以断开图中的两个顶点