我正在解决 Kleinberg 和 Tardos 的算法设计书中的练习，并遇到了这个（对我来说）不太容易的问题，即找到一条边永远不会属于图的 MST 的保证。问题是这样的：
给你一个图 G = (V, E)，每条边 e 的成本为 c_e。给定误差参数 epsilon 和 k（均 > 0），您想确定以下属性 (*) 在多项式时间内是否适用于特定边 e' = (u, v)。
(*) 即使每条边的成本最多改变 epsilon（增加或减少），并且除 e' 之外的 k 条边的成本进一步改变为一些任意不同的值，边 e' 仍然不属于 G 的任何 MST。
我知道 MST 的 cut 属性，但看不到如何将其应用于此问题。提前感谢您的想法！
感谢 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 更昂贵的边。