Prim与Kruskal算法在两类特殊MST目标下的有效性求证

问题1：最小化树中边的最大权重时，算法有效性的证明思路 #

我们称满足“树中边的最大权重最小”的生成树为最小最大生成树（MMST），以下是Prim与Kruskal算法能生成MMST的证明逻辑：

Prim算法的证明逻辑 #

• Prim算法的核心规则：每次选择连接已选顶点集与未选顶点集的最小权重边。
• 假设存在一棵MMST，其最大边权重w*小于Prim生成树的最大边权重w_p。
• 考虑Prim算法中首次加入权重为w_p的边e时，e连接的两个顶点u（已选）和v（未选）在MMST中必然存在一条路径，路径上至少有一条边跨越已选/未选顶点集，且该边的权重≤w* < w_p。
• 这与Prim算法选择当前最小权重边的规则矛盾，因此Prim生成树的最大边权重不可能大于MMST的，即Prim生成树就是MMST。

Kruskal算法的证明逻辑 #

• Kruskal算法的核心规则：按边权重从小到大排序，依次加入不形成环的边。
• 假设存在MMST的最大边权重w*小于Kruskal生成树的最大边权重w_k。
• Kruskal算法中加入w_k的边e时，说明所有权重≤w*的边无法连接e的两个顶点所在的连通分量（否则e会形成环，不会被加入）。
• 但MMST中这两个连通分量必然通过一条权重≤w*的边连接，这与上述结论矛盾，因此Kruskal生成树的最大边权重等于w*，即Kruskal生成树是MMST。

问题2：最小化树中边权重乘积时，算法的失效示例与证明思路 #

失效示例 #

考虑3顶点无向图，顶点为A、B、C，边及权重如下：

• A-B: -2
• B-C: -2
• A-C: 3

所有可能的生成树：

• 生成树1（Prim/Kruskal输出）：选择边A-B与B-C，总和为-2 + (-2) = -4，乘积为(-2)×(-2) = 4
• 生成树2：选择边A-B与A-C，总和为-2 + 3 = 1，乘积为(-2)×3 = -6
• 生成树3：选择边B-C与A-C，总和为-2 + 3 = 1，乘积为(-2)×3 = -6

显然，乘积最小的生成树是生成树2/3（乘积=-6），但Prim/Kruskal会优先选择权重最小的负边，最终得到总和最小但乘积更大的生成树1，算法失效。

证明思路 #

• 有效场景（所有权重为正数）：对每个边权重w(e)取自然对数，乘积的对数等于各边权重对数的和，即ln(Πw(e)) = Σln(w(e))。由于ln(x)在x>0时是单调递增函数，最小化乘积等价于最小化Σln(w(e))，这与MST的总和最小目标（仅需将权重替换为ln(w(e))）一致，因此Prim/Kruskal算法有效。
• 失效场景（存在负权重边）：负数相乘的奇偶性会改变乘积的正负性，可能出现总和更大但乘积更小的情况（如示例中负数+正数的组合）。此时Prim/Kruskal按权重从小到大选边的规则，会优先选择总和最小的组合，无法保证乘积最小，因此算法失效。

内容的提问来源于stack exchange，提问作者dimitrisaspas