algorithm - 两条边相连的最小生成树

Question

我想解决更难的最小生成树问题。

有 N 个顶点。还有 2M 边，编号为 1, 2, .., 2M。该图是连通的、无向的和加权的。我想选择一些边缘使图形仍然连接并使总成本尽可能小。有一个限制:编号为 2k 的边和编号为 2k-1 的边并列，因此应选择两者或两者都应不被选中。所以，如果我要选择边 3，我也必须选择边 4。

那么，使图连通的最小总成本是多少？

我的想法:

• 我们将两条边 2k 和 2k+1 称为边集。
• 如果边合并了两个不同的组件，我们就称它为有效。

• 如果两条边都有效，我们就称边集好。

  1. 首先恰好添加 m 个边集，这些边集按成本递增的顺序排列。然后按成本递增的顺序迭代所有边集，如果至少有一条边有效，则添加该集。 m 应该从 0 迭代到 M。

  2. 运行具有一些变化的 kruskal 算法:边 e 的成本变化。

     • 如果包含 e 的边集好，则成本为:(边集的成本)/2。
     • 否则，成本是:(边集的成本)。
     • 即使成本发生变化，我也无法证明 kruskal 算法是否正确。

抱歉英语不好，但我想解决这个问题。是NP-hard还是什么的，还是有什么好的解决办法？ :D 在此先感谢您!

Answer 1

正如我之前推测的那样，这个问题是 NP-hard 问题。我不确定不可近似性；有一个非常简单的 2 近似值(将每对分成两半，保留两半的全部成本，然后运行您最喜欢的 Vanilla MST 算法)。

给定该问题的算法，我们可以如下求解 NP-hard 哈密顿循环问题。

设 G = (V, E) 为哈密顿循环的实例。克隆所有其他顶点，用 vi' 表示 vi 的克隆。我们复制每条边 e = {vi, vj}(制作一个多重图；我们可以以清晰度为代价用简单的图进行这种简化)，并且让 v0 成为任意原始顶点，我们将一个副本与 {v0, vi '}，另一个是 {v0, vj'}。

没有 MST 可以使用少于 n 对，一对将每个克隆顶点连接到 v0。有趣的是，像这样具有 n 对的候选对的另一半可以解释为 G 的定向子图，其中每个顶点的出度为 1(使用克隆位中的索引作为尾部)。此图连接原始顶点当且仅当它们是汉密尔顿循环。

---

有多种应用整数规划的方法。这是一个简单的和一个更复杂的。首先，如果边对 2i-1, 2i 是 1，我们为每个 i 制定一个二进制变量 x_i选择。问题模板看起来像

minimize sum_i w_i x_i (drop the w_i if the problem is unweighted)
subject to
<connectivity>
for all i, x_i in {0, 1}.

当然，我已经忽略了有趣的约束 :)。强制连通性的一种方法是首先在没有约束的情况下求解此公式，然后检查解决方案。如果它已连接，那就太好了——我们完成了。否则，找到一组顶点 S 使得 S 与其补码之间没有边，并添加约束

sum_{i such that x_i connects S with its complement} x_i >= 1

然后重复。

另一种方法是在解决整数程序的线性松弛问题的求解器内部生成这样的约束。通常 MIP 库具有允许这样做的功能。然而，分数问题具有分数连通性，这意味着找到最小切割来检查可行性。我希望这种方法更快，但我必须道歉，因为我没有精力详细描述它。