algorithm - 如何证明 MST 上总存在一条极小极大路径

Question

A minimax path在无向图中是两个顶点 v, w 之间的路径，它最小化路径上边的最大权重。

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

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

Answer 1

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

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

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

设B为Q中权重最大的边(图中边的长度代表其权重):

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

现在有 2 个条件需要考虑:

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

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

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

对于不在 T 中的 minimax 路径上的每条边 A，可以按照第 2 点中的描述进行边替换，从而创建一个 minimax 路径，它将完全在 T 上。