保证边不是最小生成树的一部分

Question

保证边不是最小生成树的一部分

algorithmgraphminimum-spanning-tree

4

我在解Kleinberg和Tardos的《算法设计》书中的练习时，遇到一道不太容易（对我来说）的问题，涉及到如何找到一个保证边不会属于图中MST的问题。问题描述如下：

给定成本为c_e的每条边e的图G =（V，E）。给定误差参数epsilon和k（均> 0），您希望在多项式时间内确定特定边e' =（u，v）是否满足以下属性(*)。

即使每条边的成本最多增加或减少epsilon，并且除e'之外的k条边的成本进一步更改为某些任意不同的值，边e'仍然不会属于G的任何MST。

我知道MST的切割属性，但不知道如何应用到这个问题上。谢谢您提供的想法！

- samarth.robo

2

一个足够的（但可能是不必要的强）条件，以便在k个改变边的情况下仍能保持连通的是，e是k + 1个或更多成对边不相交（除了e本身）的循环中的最重边。然后，改变任何k条边最多只会使e在其中k个循环中不再是最重的，从而留下至少1个循环，在其中它仍然是最重的，因此永远不会出现在任何最小生成树中。 - j_random_hacker

1

@j_random_hacker：好的，我看到了解决方案的曙光。这个问题的答案展示了如何将循环查找建模为网络流问题。假设您将所有边缘的容量设置为1，将e'的一端作为源，另一端作为汇，并查看是否获得值为k+1的循环。如果您确实获得了该循环，则意味着e'是k+1个边不相交的循环的一部分（除了e'本身）。但是，如何确保它是最昂贵的呢？ - samarth.robo

1

这听起来是可行的方法。为了确保 e 是每个环中最重的边，只需在执行网络流计算之前（暂时）删除任何比它更重的边即可！ :) - j_random_hacker

@j_random_hacker：太棒了！我现在会将其添加为答案。谢谢！ - samarth.robo

不用谢，但记得也要处理 epsilon 部分！虽然我认为这是更容易处理的条件。 - j_random_hacker

1个回答

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

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

- samarth.robo · Answer 1

最终得出了答案，感谢 j_random_hacker 的评论。

答案基本上使用了 MST 的循环属性 - 如果一条边是 G 中一个循环中最昂贵的边，则它不能属于 G 的任何 MST。

更改 k 条边的成本的规定意味着我们必须证明 e' 是至少 k+1 个循环中最昂贵的边，这些循环除了 e' 本身之外都是边不相交的。这样，即使对 k 条边进行任意更改导致 e' 不再是 k 个循环中最昂贵的边，它仍将是最后一个循环中最昂贵的边。

给定图 G、边 e' 和参数 k 和 epsilon（均 > 0）：

暂时删除 G 中所有比 e' 更昂贵的边（这确保了无论在哪个环中，e' 都是最昂贵的）
现在，将 e' 的一端设置为源（s），将另一端设置为汇（t）。将所有边的容量设置为 1。流整数性保证，由于所有容量都是整数，我们将得到一个整数流。
查看是否获得了至少 k+1 值的流。如果是，请进行流分解，可以得到从 s 到 t 的与边不相交的路径数量和流的值相同。通过添加 e' 将所有这些路径转换为循环-这样，您就有了 k+1（或更多）个具有 e' 最昂贵边并且除 e' 外都不相交的环。现在可以安全地说属性 (*) 适用于 e'。

如果 epsilon 是整数，则我有一种处理方法。在步骤 1 中，删除所有比 cost(e) + 2*epsilon 更昂贵的边。