给定以间隔作为边成本的图形检查 MST 有效性
Check MST validity given a graph with intervals as edges costs
我简直是在绞尽脑汁想弄清楚这个问题。
给定一个无向连通图 G ， G 中的所有边都具有未知成本，但已知每条边的每个成本的区间，例如边 e 的成本在闭区间 [i,j] 中，其中 i 和 j 是实数。我还得到了一个名为 T 的 G 生成树。我需要创建一个算法来检查 T 是否可以是 G 的最小生成树。
我尝试将此问题与网络流量联系起来，但无法找到解决方案。是否有任何提示可以找到解决此类问题的方法？
这个问题可以用linear programming来解决。检查 T 是否可以是最小生成树相当于检查一组 |E| 上的一组线性约束的可行性。变量，一个对应于图的每条边。变量 x(u,v) 对应于边 (u,v) 的权重。也就是说，线性规划的可行解决方案是为图边分配权重，使得 T 是最小生成树。因此，首先，每个变量 x(u,v) 都被限制在指定的区间内。
当且仅当 T 是求解程序的分配下的最小生成树时，我将在稍后指定的其他约束被设计为满足。
要理解为什么在满足以下约束的每个分配下 T 必须是最小生成树，您必须说服自己以下 属性 个最小生成树：
生成树 T 是最小生成树当且仅当对于不在 T 中的每条边 (u,v) 和 T 中从 u 到 v 的路径中的每条边 e，w(u,v)>=w(e). 属性 遵循 the cut property.
因此，要检查 T 是否可以是最小生成树，应该检查由以下一组约束定义的线性程序的可行性。
- 对于图中的每条边，
i(u,v)<=x(u,v)<=j(u,v)。
- 对于不在 T 中的每条边
(u,v) 和 T 中从 u 到 v 的路径中的每条边 e，x(u,v)>=x(e)。
我简直是在绞尽脑汁想弄清楚这个问题。 给定一个无向连通图 G ， G 中的所有边都具有未知成本，但已知每条边的每个成本的区间，例如边 e 的成本在闭区间 [i,j] 中，其中 i 和 j 是实数。我还得到了一个名为 T 的 G 生成树。我需要创建一个算法来检查 T 是否可以是 G 的最小生成树。 我尝试将此问题与网络流量联系起来，但无法找到解决方案。是否有任何提示可以找到解决此类问题的方法？
这个问题可以用linear programming来解决。检查 T 是否可以是最小生成树相当于检查一组 |E| 上的一组线性约束的可行性。变量，一个对应于图的每条边。变量 x(u,v) 对应于边 (u,v) 的权重。也就是说，线性规划的可行解决方案是为图边分配权重，使得 T 是最小生成树。因此，首先，每个变量 x(u,v) 都被限制在指定的区间内。
当且仅当 T 是求解程序的分配下的最小生成树时，我将在稍后指定的其他约束被设计为满足。
要理解为什么在满足以下约束的每个分配下 T 必须是最小生成树，您必须说服自己以下 属性 个最小生成树：
生成树 T 是最小生成树当且仅当对于不在 T 中的每条边 (u,v) 和 T 中从 u 到 v 的路径中的每条边 e，w(u,v)>=w(e). 属性 遵循 the cut property.
因此，要检查 T 是否可以是最小生成树，应该检查由以下一组约束定义的线性程序的可行性。
- 对于图中的每条边，
i(u,v)<=x(u,v)<=j(u,v)。 - 对于不在 T 中的每条边
(u,v)和 T 中从u到v的路径中的每条边e，x(u,v)>=x(e)。