穿越图割的最小生成树正好经过N次

Question

穿越图割的最小生成树正好经过N次

algorithmgraph-theoryminimum-spanning-tree

6

给定两个相连的加权图和一组可以在两个图之间“过河”的顶点对，任务是找到一个由这些交叉连接而成的图的最小生成树（MST），其中包含恰好N个过河的交叉点。对于给定的排列，总是存在解决方案。

在下面的示例中，左侧图有顶点（0, 1, 2, 3），右侧图有顶点（4, 5, 6, 7, 8）。边3-4、3-5、2-4、2-5可供选择，且N = 2。以红色表示的最小生成树恰好包含两个过河的交叉点。

首先，通过最小生成树的切割属性，我认为要选择的交叉点是其中最低的 N 个。

其次，如何强制让 Prim 算法在寻找最小生成树时选择某些边呢？你不能预先连接已选的交叉点，因为它可能只会选择一个。

我的第一个想法是修改算法，使其在过程中始终选择已选的交叉点（如上图中的3-5和2-4），但这可能会创建循环，对吧？它必须知道在强制选择某些顶点时不要创建循环。

我的第二个想法是先找到左侧和右侧的最小生成树，然后再尝试连接它们——但这样做可能会创建循环，对吧？如果用最大值的边来打破循环，那是否就可以自动得出答案了呢？因为你可以确保两侧都有它们的最小生成树，它们通过最便宜的路径相连，并且没有循环。

- tomashauser

关于你的其他想法：1）强制 Prim 算法以任何方式选择特定边缘而不是限制顶点集可能难以有效实施。我不知道它在合理复杂度内是否可行。2）如果您先找到一侧的 MST，然后是另一侧，然后将它们连接起来，那么这将迫使 N 总是为 0。3）通过删除环上最重的边缘来断开循环也可能是一个相当困难的问题。 - Maurycyt

2

第一直觉是错误的。例如，将边权重为9更改为2。然后选择穿过河流的边2和6会强制您通过节点4进入右侧图形。如果您将从节点4出发的边从权重4更改为400，将5更改为500，则立即明显的是，使用边7和2穿过河流要比使用边6和2好得多。 - user3386109

看起来很棘手。你也许可以用加权拟阵交集在多项式时间内解决，但肯定有更好的方法... - David Eisenstat

1

您确实可以使用加权拟阵交集来获得多项式时间算法。第一个拟阵是生成树拟阵（当然）；第二个拟阵是将非交叉边的数量限制为|V|-1-n的分区拟阵。 - David Eisenstat

让我先解释一下：你实际上需要一个跨越树，还是具有恰好k个交叉点的最小跨越子图（一般情况下可能比恰好k个交叉点的最小跨越树更轻）？ - David Eisenstat

显示剩余8条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

这是一个比加权 matroid 交集算法更简单的算法。让 C 成为交叉边的集合，如果使用动态树的高效实现，则运行时间为 O((|E| + k |C|) log |V|)。(我有意降低了运行时间；你可以使用比 Prim 或 Kruskal 更好的初始化算法。)

问题是：

min_x ∑_e∈E w_e x_e subject to (*) ∑_e∈C x_e = k x ∈ {0,1}^E 表示生成树

除了标记为 (*) 的约束条件外，这是一个经典的最小生成树问题。我们使用拉格朗日乘数λ重新描述(*)。

min_x max_λ ∑_e∈E w_e x_e + λ (∑_e∈C x_e − k) subject to x ∈ {0,1}^E 表示生成树 λ ∈ R

直观地说，我们选择x，对手通过选择λ进行回应。如果我们选择少于k个交叉边，则对手将目标函数变为λ → -∞。如果我们选择多于k个交叉边，则对手将目标函数变为λ → ∞。因此，我们应该恰好选择k个交叉边。

这个问题有一个对偶问题：

max_λ min_x ∑_e∈E w_e x_e + λ (∑_e∈C x_e − k) subject to x ∈ {0,1}^E 表示生成树 λ ∈ R

这里对手选择λ，我们通过选择x进行回应。直观地说，这对我们来说应该严格更好，但由于有趣的数学原因，完美博弈时完全相同。现在，技巧在于我们可以取乘数λ并将其贡献(除了λ k之外，在x中是常量)折叠到权重w中，从而使我们恢复标准的最小生成树问题。

算法

这是一种动态算法。首先用最小生成树来初始化，从轻到重考虑 E ∖ C 中的边，然后考虑 C 中的边。当 λ → ∞ 时，这就是极限下的最小生成树。如果有超过 k 条交叉边，则没有解决方案；该生成树所具有的交叉边数量尽可能少。我们在滑动 λ 向 −∞ 的过程中维护最小生成树，直到出现恰好 k 条交叉边（最优解）或到达极限位置（无解）为止。

通常情况下，我们不会通过小增量地改变 λ。相反，我们寻找下一个“有趣事件”的 λ 值，即查找最大 λ 值，使得存在一条不在当前生成树中的 C 中的边 e 和一条在其基本环中的不在 E ∖ C 中的边 e′，使得 w(e) + λ = w(e′)。我们将 e′ 置换成 e。数据结构上，动态树（理论上）是一种使这些操作快速高效的方法。最多循环 k 次，我们遍历 C 中的 e 并对每个进行 O(log |V|)-时间的查询，随后进行两次 O(log |V|)-时间的拓扑变化。