Given a disconnected graph, find the minimum operations to rearrange the vertices such that the graph becomes connected

user_15991783 0
Viewed 462

I'm working on a graph theory problem with a given disconnected unweighted, undirected graph (given an edge list). The following operation can be made on the graph:

A set of edges represented by two vertex pairs (i, j) and (x, y) can be switched into (i, y) and (x, j)

The following are the tasks that need to be accomplished:

  1. Determine if it is possible to connect the graph.
  2. If yes, find the minimum number of operations to connect the graph.
  3. Output the edges used per operation in the following order: i j x y

An additional constraint is that a vertex cannot be connected to itself. Vertices can be up to n = 10^5

I have already implemented the switch function defined above, however, my current solution is very inefficient and may not be applicable to all possible inputs. It basically checks for any four vertices with multiple connections and applies the switch operation, then runs a DFS (depth-first search) algorithm to check if the graph is connected or not, so it runs a DFS every time it makes an operation. Additionally, this doesn't deal with the minimum operations, it just does operations until the graph becomes connected. Are there any implementation tips or algorithms that can help in solving the problem, preferably in Python?

shortest-path graph-theory algorithm python
1 Answers

Say your graph G has n vertices, e edges, and k > 1 components.

A solution is possible iff there are no isolated vertices and e >= n-1. It will take k-1 switches.

If e < n-1 then there aren't enough edges for a connected graph to exist. If there's an isolated vertex, switch operations can't affect it so it will remain isolated.

Otherwise, repeatedly perform the following switch: One edge should belong to a component where its removal won't disconnect the component. This is guaranteed to exist if there are multiple components and e >= n-1. The other edge can belong to any other component (and it doesn't matter if its removal would disconnect the component). Performing the switch operation will merge these components, reducing the total number of components by one.

We perform k-1 switches, reducing the number of components from k to 1, at which point the graph is connected.

--- O(V+E) approach ---

  • Confirm there are no isolated vertices and that E >= V-1.
  • Use BFS to split the input graph G into its components. While doing this, keep track of every edge that completes a cycle (connects to an already visited vertex). Call these 'swappable edges'
  • Repeatedly perform swap operations where one edge is swappable, and the other is an arbitrary edge of some other component.
  • Note that if the other edge is also swappable, then both new edges after the swap are on a cycle. Choose one of them (arbitrarily) to add to the list of swappable edges.
  • Each swap reduces the number of swappable edges by one and the number of components by one. Keep going until you're down to one component.
user_20410770
Related