如何证明 MST 上总存在一条极小极大路径
How to prove there always exists a minimax path completely on the MST
无向图中的一条minimax path是两个顶点v,w之间的路径，使路径上的边的最大权值最小
设T为给定图G=(V,E)的最小生成树。我如何证明，对于 v 中的任意一对顶点 v, w，v 之间总是存在极小极大路径 和 w 即完全在 T.
我试图假设 T 上完全没有极小极大路径，但我不知道如何得出矛盾。
假设在最小生成树外有一条minimax路径比最小生成树上的路径做的更好。从树中删除最小生成树路径上成本最高的边，将图拆分为两个连接的组件。您可以使用 minimax 路径从一个组件到达另一个组件。当您沿着这条路径前进时，必须有一条边离开一个组件并进入另一个组件。将这条边添加到最小生成树中。该图现在再次连接起来，最小生成树的总成本降低了，因为极小极大路径上的每条边的成本都低于最小生成树上成本最高的边的成本。所以我们有一个矛盾，不存在这样的极小极大路径。
假设在顶点 u 和 v 之间存在一条极小极大路径 P完全在最小生成树上 T.
这意味着 A(p, q) 在 P 中存在一条不在 T[ 中的边=65=]。
设Q为T中从p到的路径q.
设B为Q中权重最大的一条边（图中边的长度代表其权重） :
T 标记为绿色
P = (u,p,q,v)
现在有2个条件需要考虑：
weight(B) > weight(A)：那么T不是最小生成树.如果您要从 T 中删除 B 并改为添加 A ，您仍然会有一个生成树，但它的总重量会减少。由于这是一个矛盾（T 被给出为 最小 生成树，剩下的唯一可能性是：
weight(B) <= weight(A)：在这种情况下，您可以从 P 并将 Q 的边添加到它，它仍然是一条极小极大路径，因为我们没有包含具有更大权重的边比以前已经在这条路上。
请注意，此替换会使极小极大路径变长，但这不是问题。两个顶点之间可以有几条路径，它们都最小化最大边权重——没有要求最小最大路径是其中最短的路径。
对于不在 T 中的极小极大路径上的每条边 A，可以按照第 2 点中的描述进行边替换，从而创建一个完全在 T.
上的极小极大路径
无向图中的一条minimax path是两个顶点v,w之间的路径，使路径上的边的最大权值最小
设T为给定图G=(V,E)的最小生成树。我如何证明，对于 v 中的任意一对顶点 v, w，v 之间总是存在极小极大路径 和 w 即完全在 T.
我试图假设 T 上完全没有极小极大路径，但我不知道如何得出矛盾。
假设在最小生成树外有一条minimax路径比最小生成树上的路径做的更好。从树中删除最小生成树路径上成本最高的边，将图拆分为两个连接的组件。您可以使用 minimax 路径从一个组件到达另一个组件。当您沿着这条路径前进时，必须有一条边离开一个组件并进入另一个组件。将这条边添加到最小生成树中。该图现在再次连接起来，最小生成树的总成本降低了，因为极小极大路径上的每条边的成本都低于最小生成树上成本最高的边的成本。所以我们有一个矛盾，不存在这样的极小极大路径。
假设在顶点 u 和 v 之间存在一条极小极大路径 P完全在最小生成树上 T.
这意味着 A(p, q) 在 P 中存在一条不在 T[ 中的边=65=]。
设Q为T中从p到的路径q.
设B为Q中权重最大的一条边（图中边的长度代表其权重） :
T 标记为绿色
P = (u,p,q,v)
现在有2个条件需要考虑：
weight(B) > weight(A)：那么T不是最小生成树.如果您要从 T 中删除 B 并改为添加 A ，您仍然会有一个生成树，但它的总重量会减少。由于这是一个矛盾（T 被给出为 最小 生成树，剩下的唯一可能性是：
weight(B) <= weight(A)：在这种情况下，您可以从 P 并将 Q 的边添加到它，它仍然是一条极小极大路径，因为我们没有包含具有更大权重的边比以前已经在这条路上。
请注意，此替换会使极小极大路径变长，但这不是问题。两个顶点之间可以有几条路径，它们都最小化最大边权重——没有要求最小最大路径是其中最短的路径。
对于不在 T 中的极小极大路径上的每条边 A，可以按照第 2 点中的描述进行边替换，从而创建一个完全在 T.
上的极小极大路径