algorithm - 给定一个以区间为边成本的图，检查 MST 有效性

Question

我真的很想弄清楚这个问题。给定一个无向和连通图 G ，G 中的所有边都有未知的成本，但已知每条边的每个成本的区间，例如边 e 的成本在闭区间 [i,j] 中，其中 i 和 j 是实数。我还得到了一个名为 T 的 G 生成树。我需要创建一个算法来检查 T 是否可以是 G 的最小生成树。我尝试将此问题连接到网络流，但我无法找到解决方案。是否有任何提示可以找到解决此类问题的方法？

标签： algorithmminimum-spanning-tree

Answer 1

这个问题可以用线性规划来解决。检查 T 是否可以是最小生成树相当于检查一组线性约束对一组 |E| 的可行性。变量，一个用于图的每条边。变量 x(u,v) 对应于边 (u,v) 的权重。也就是说，线性规划的可行解决方案是将权重分配给图边，使得 T 是最小生成树。因此，首先，每个变量 x(u,v) 都被限制在指定的区间内。

我将很快指定的其他约束旨在满足当且仅当 T 是求解程序的分配下的最小生成树。

要理解为什么在满足以下约束 T 的每个分配下必须是最小生成树，您必须让自己相信最小生成树的以下属性：

生成树 T 是最小生成树当且仅当对于不在 T 中的每条边 (u,v) 以及在 Te中从 u 到 v 的路径中的每条边w(u,v)>=w(e)。此属性来自cut 属性。

因此，要检查 T 是否可以是最小生成树，应该检查由以下一组约束定义的线性规划的可行性。

• 对于图中的每条边，i(u,v)<=x(u,v)<=j(u,v)。
• 对于(u,v)不在 T 中的每条边和在 T中的从到e路径中的每条边，.uvx(u,v)>=x(e)