考虑一个连通的无向图G=VE每条边的边权w≥0我们计算G的最小生成树和从 seV到其他点的最短路。接下来我们把每条边权重增加1a原来那个最下生成树还是最小生成树吗如果回答是请证明回答不是请给出例子。b原来的最短路还是最短路吗如果回答是请证明回答不是请给出例子。并给出解题思路

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

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

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

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

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

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

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

解题思路：

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

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