如何证明MST上总存在完全极小极大路径

Question

无向图中的极小极大路径是两个顶点v、w之间的路径 ，其最小化路径上边的最大权重。

令T为给定图G=(V,E)的最小生成树。我如何证明，对于V中的任何一对顶点v, w ，在v和w之间始终存在一条完全在T上的极小极大路径。

我试图假设T上完全没有极小极大路径，但我不知道如何得出矛盾。

Answer 1

假设顶点u和v之间存在一条不完全在最小生成树T上的极小极大路径P。

这意味着P中有一条边A(p, q)不在T中。

令Q为T中从p到q的路径。

设B为Q中权重最大的边（在图像图中，边的长度代表其权重）：

                    T 以绿色标记
                    P = (u,p,q,v)

现在有两个条件需要考虑：

1. 权重(B) > 权重(A)：在这种情况下，T不是最小生成树。如果你从T中删除B并添加A，你仍然会有一棵生成树，但它的总权重会减少。由于这是一个矛盾（T被指定为最小生成树），所以剩下的唯一可能性是：

2. 权重(B) <= 权重(A)：在这种情况下，您可以从P中删除A并将Q中的边添加到其中，它仍然是一条极小极大路径，因为我们没有包含具有更大权重的边比之前已经在这条路上。

   请注意，这种替换将使极小极大路径更长，但这不是问题。两个顶点之间可以有多条路径，它们都最小化最大边权重——不要求最小最大路径是其中最短的。

对于不在T中的极小极大路径上的每条边A，可以按照第 2 点中所述进行边替换，从而创建完全在T上的极小极大路径。