algorithm - 为什么当我们将 G 中每条边的成本更改为 c'= log17(c)时，G 中的每个 MST 仍然是 G' 中的 MST(反之亦然)？

Question

备注:c'是以17为底的logc
MST 表示(最小生成树)
当我们使用线性函数对每条边的代价进行变换时，很容易证明结论是正确的。
但是对数函数不是线性函数，我不明白为什么这个结论是正确的。
补充说明:

I did not consider specific algorithms, such as the greedy algorithm. I simply consider the relationship between the sum of the weights of the two trees after transformation.Numerically if (a + b) > (c + d) , (log a + log b) maybe not > ( logc + logd) .
If a tree generated by G has two edge a and b ,another tree generated by G has c and d，a + b < c + d and the first tree is a MST,but in transformed graph G' ,the sum of weights of edges of second tree may be smaller.
Because of this, I want to construct a counterexample based on "if (a + b)> (c + d), (log a + log b) maybe not> (logc + logd) ", but I failed.

Answer 1

表征生成树 T 是最小生成树时的一种方法是，对于不在 T 中的每条边 e，由 e 和 T 的边(e 相对于 T 的基本环)形成的环没有更昂贵的边比e。使用这个特征，我希望你看到如何证明用任何递增函数转换成本可以保留最小生成树。
有一个单行证明这个条件是必要的。如果基本循环包含更昂贵的边，我们可以用 e 替换它并得到一个成本小于 T 的生成树。
这个条件是否充分不太明显，因为乍一看，我们似乎试图从局部最优条件证明全局最优。为了证明这个命题，设T为满足条件的生成树，设T'为最小生成树，设G'为边是T和T'边的并集的图。在 G' 上运行 Kruskal 算法，通过偏向 T 中的边而不是不在 T 中的边来打破关系。让 T'' 成为 G' 中生成的最小生成树。由于T'是G'中的一棵生成树，T''的代价不大于T'，因此T''是G'中的最小生成树，也是G'中的最小生成树。
假设相反，T''≠T。那么在T 中存在一条边，但在T'' 中不存在。让 e 成为克鲁斯卡尔算法考虑的第一个这样的边。在考虑e的时候，它在从T''中选出的边上形成了一个循环C。由于 T 是无环的，因此 C\T 是非空的。通过打破平局标准，我们知道 C\T 中的每条边的成本都小于 e。观察到C\T中的某条边e'在T\{e}的两个连通分量中的每一个都必须有一个端点，我们推断e'关于T的基本环包含e，这违反了局部最优性条件.总之，T = T''，因此是 G 中的最小生成树。
如果你想要更深入的了解，这个逻辑在 matroids 的理论中被抽象出来了。 .