如何在无向图中移除最少的边以创建 k 个连通分量？

Question

如何解决问题：删除最少的边以创建 k 个连通分量？该图可能已经是一棵森林，但不一定具有 k 个连通分量，并且可能具有循环。它是无权和无向的。

- fool_of_a_took

Answer 1

• 如果图形已经至少有k个组件，则答案为0。
• 如果图形是一棵树，则答案为k-1。
• 如果图形是具有n个节点的完全图，则答案为n-1 + n-2 + ... + n-k+1 = (n(n-1) - (n-k)(n-k+1))/2。
• 在没有假设的情况下，答案可以是0到(n(n-1) - (n-k)(n-k+1))/2之间的任何数字。

- Stef

Answer 2

如果原始图是一棵树，则删除每条边将使连接组件的数量增加1。在删除k-1条边后，该图将变成具有k个连接组件的森林。

- Ashwin Ganesan

---

我同意，但如果它不是一棵树呢？ - fool_of_a_took

@fool_of_a_took，那么答案不仅取决于k，还需要更多的信息才能回答这个问题。 - Ashwin Ganesan

Answer 3

我们可以使用DSU（不相交集合）这种东西。

- Hitesh Kumar

---

根据目前的写法，你的回答不够清晰。请编辑以添加更多细节，帮助其他人理解这如何回答所提出的问题。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - Community