How to find edge connectivity between 2 given vertex

1
votes

Edge connectivity is minimum number of edge to be removed to divide graph in 2 or more components. As of now I have found an algorithm for edge connectivity irrespective of vertex: http://www.sanfoundry.com/java-program-find-edge-connectivity-graph/

What is the best method I can use to proceed with, to find the edge connectivity between 2 vertices?

Edge Connectivity between 2 vertex(v1, v2) - Means

If cutting any edge/edges in Graph G, generates two components G1 & G2.

Here ( v1 ∈ G1 and v2 ∈ G2 ) OR ( v2 ∈ G1 and v1 ∈ G2 )

1
javaalgorithmgraphgraph-theory
To find edge connectivity between two vertices, use breadth-first search (BFS). – Nayuki
It is indeed the minimum cut you want. Which is the minimum number of edges needed to disconnect two vertices. BFS will only tell you if those two vertices are connected. You may use it to see if the connectivity is greater than zero, then use a flow algorithm to fin minum cut, using your two vertices as source and sink, the BFS ordering might help on converting your undirected graph into a directed one, and thus apply ford fulkerson, as suggested in the first answer. – Javier Cano

1 Answers

2
votes

You're describing the minimum cut problem. It's equivalent to finding the maximum flow, and the Ford Fulkerson algorithm can find it.