图论问题：边权增加后的最小生成树和最短路

考虑一个连通的无向图 G = (V, E)，每条边的边权 w ≥ 0。我们计算 G 的最小生成树和从 seV 到其他点的最短路。接下来我们把每条边权重增加 1.

(a) 原来的那个最下生成树还是最小生成树吗? 如果回答是请证明，回答不是请给出例子。 (b) 原来的最短路还是最短路吗? 如果回答是请证明，回答不是请给出例子。

解题思路：

(a) 最小生成树不一定还是最小生成树。考虑一个图，有 4 个节点，连边如下：

其中边权为红色数字。原图最小生成树为：

现在将每条边权增加 1，得到的图为：

可以发现，原来的最小生成树不再是最小生成树，新的最小生成树为：

(b) 原来的最短路不一定还是最短路。考虑一个图，有 4 个节点，连边如下：

其中边权为红色数字。从节点 1 到节点 4 的最短路为 1-2-4，路径长度为 3。现在将每条边权增加 1，得到的图为：

可以发现，原来的最短路不再是最短路，新的最短路为 1-3-4，路径长度为 4。

解题思路：

(a) 对于最小生成树，我们可以通过反证法来证明。假设原来的最小生成树不再是最小生成树，那么一定存在一棵树 T，其权值比原来的最小生成树小。我们考虑在新图中，将原来的最小生成树上的边的权值都增加 1，那么这些边的权值仍然相等，因此 T 在新图中的总权值也比最小生成树小，与最小生成树的定义矛盾。因此原来的最小生成树还是最小生成树。

(b) 对于最短路，我们可以通过构造反例来证明。我们可以构造一个图，使得原来的最短路经过的边的权值都比其他边小，因此在增加边权后，原来的最短路不再是最短路。