使边权重唯一的线性算法

Question

我有一个加权图，我想为该图计算一个新的加权函数，使得边权重不同，并且新图中的每个 MST 都对应于旧图中的一个 MST。

找不到可行的算法。我把所有的重量都加倍了，但这不会让它们与众不同。我还尝试将权重加倍并向具有相同权重的边添加不同的常量，但这也不对。

新图将只有 1 个 MST，因为所有边都是不同的。

Answer 1

我们肯定不能保证旧图中所有的MST都是新图中的MST；一个反例是三个顶点的完全图，其中所有边具有相等的权重。所以我假设你不需要构造给出所有的MST，因为这在一般情况下是不可能的。

我们能否始终使新图的 MST 成为旧图的子集？如果我们可以在没有 MST 的情况下构建一个图，这将很容易。当然，这没有任何意义，也是不可能的，因为所有图都至少有一个 MST。是否可以更改边权重，以便只有一个旧图的 MST 是新图的 MST？我建议这在一般情况下是可能的。

确定旧图的一些MST。
构造一个具有相同边和顶点的新图，但权重分配如下：
- 如果新图中的边属于步骤1中确定的MST，则为其赋予一个介于1和n之间的唯一权重，图中的边数。
- 否则，为新图中的边赋予大于或等于n^2的唯一权重，即图中边数的平方。

没有证明，这似乎应该保证只有旧图中指定的MST是新图中的MST，因此新图中的每个MST（只有一个）是中的MST旧图。

现在，有人可能会问我们是否可以在有额外限制的情况下执行此操作：

甚至可以提出优化问题：

我对尝试这些问题犹豫不决，我认为这些问题要困难得多。

Answer 2

非常简单：我们将所有权重乘以一个足够大的因子 K 以确保我们的小更改不会影响 MST 的有效性。我会过分强调这一点：

K = max(<sum of all graph weights>, 
        <quantity of edges>)
        + 1

以任意顺序对 N 边编号，0 到 N-1。对于每个边缘权重，添加边缘编号。证明

很简单

边缘权重现在是唯一的（不同权重之间的新差异大于变化）；
新图中的任何 MST 都直接映射到新图中的相应 MST 旧路径（每个新路径和是旧路径的 K 倍，再加上小于 K 的数量——不影响任何两条路径上的比较（小于或大于））。

是的，这太过分了：您可以对 K 的值进行相当大的限制。然而，让它变大会减少初中代数学生可以遵循的引理的正确性证明。

Linear algorithm to make edge weights unique