How do I approach the problem: Minimum amount of edges to remove to create k connected components? The graph might already be a forest, though not necessarily one with k connected components, and may have cycles. It is unweighted and undirected.
Minimum amount of edges to remove to create k connected components in an undirected graph?
Viewed 255
2 Answers
If the original graph is a tree, then the removal of each edge will increase the number of connected components by 1. After removing k-1 edges, the graph will become a forest with k connected components.
- If the graph already has at least k components, then the answer is 0.
- If the graph is a tree, then the answer is
k-1. - If the graph is the complete graph with
nnodes, then the answer isn-1 + n-2 + ... + n-k+1 = (n(n-1) - (n-k)(n-k+1))/2. - Without assumption, the answer can be any number between 0 and
(n(n-1) - (n-k)(n-k+1))/2.
Related