如何找到 2 个给定顶点之间的边连接

Question

边连通性是要移除以将图形分成 2 个或更多组件的最小边数。截至目前，我已经找到了一种与顶点无关的边连接算法：http://www.sanfoundry.com/java-program-find-edge-connectivity-graph/

找到 2 个顶点之间的边连通性的最佳方法是什么？

2 个顶点之间的边连通性(v1, v2) - 均值

如果切割图 G 中的任何 edge/edges，将生成两个分量 G1 和 G2。

这里 (v1 ∈ G1 and v2 ∈ G2 ) OR ( v2 ∈ G1 and v1 ∈ G2 )

Answer 1

你描述的minimum cut problem. It's equivalent to finding the maximum flow, and the Ford Fulkerson algorithm可以找到它。