给定图$G$和$G$的一棵最小生成树$T$，假设减小了$T$中一条边的权重。证明：$T$仍然是$G$的一棵最小生成树。更形式化地，设$T$为$G$的一棵最小生成树，$G$的边权重由权重函数$w$给出。选择一条边$(x，y)∈T$和一个正数$k$，并定义下述的权重函数$w'$： $w'(u,v)=\begin{cases} w(u,v)& \text{若(u,v) != (x,y)}\\w(x,y)-k& \text{若(u,v)=(x,y)} \end{cases}$ 证明：$T$仍然是$...-Go服务器开发

首先，我们可以观察到在新的权重函数$w'$下，边$(x, y)$的权重变为了$w(x, y) - k$。根据题目的要求，我们需要证明在新的权重函数下，$T$仍然是$G$的一棵最小生成树。

我们可以使用反证法来证明这个结论。假设存在另外一棵生成树$T'$比$T$更小（即总权重更小）。那么我们可以找到一条边$(u, v)$属于$T'$但不属于$T$。

考虑这条边$(u, v)$，有两种情况：

如果$(u, v) = (x, y)$，也就是说$(u, v)$正好是原来被修改了权重的那条边。由于我们减小了$(x, y)$的权重$k$，所以新的边$(u, v)$满足 $w'(u,v) = w(x,y)-k < w(u,v)$。这意味着在新的权重函数下，边$(u,v)$比原来更轻，所以如果替换掉原来的边$(x,y)$并加上边$(u,v)$后，得到的生成树会比原来更小。但这与我们假设中的生成树 $T'$ 比 $T$ 更小矛盾。
如果 $(u,v) \neq (x,y)$，也就是说$(u, v)$不是原来被修改了权重的那条边。根据题目条件，这条边在原来的生成树 $T$ 中存在。根据最小生成树的性质，在生成树中任意两个节点之间只有一条唯一路径连接。那么在生成树 $T'$ 中也必然存在一条路径连接顶点 $u$ 和 $v$。假设我们从原来的生成树 $T$ 中删除边 $(u, v)$，然后添加边 $(x, y)$ 构成新的树 $T''$。根据题目给定，新边 $(x, y)$ 的权重为 $w(x, y) - k$，而删除掉的边 $(u,v)$ 在原图中权重为 $w(u,v)$。由于我们假设了生成树 $T'$ 比生成树 $T$ 更小，所以总权重应该满足： $$\text{total weight}(T'') = \text{total weight}(T) - w(u,v) + w(x,y) - k < \text{total weight}(T)$$ 这与我们假设中的生成树 $T’$ 比 $T$ 更小矛盾。

因此，在所有可能情况下都导致矛盾，我们可以得出结论：在新的权重函数下，生成树 T 仍然是 G 的一棵最小生成树。

以下是使用Go语言实现的示例代码：

package main
import (
	"fmt"
)
type Edge struct {
	u, v, weight int
}
func find(parent []int, i int) int {
	if parent[i] == i {
		return i
	}
	return find(parent, parent[i])
}
func union(parent []int, rank []int, x int, y int) {
	xRoot := find(parent, x)
	yRoot := find(parent, y)
	if rank[xRoot] < rank[yRoot] {
		parent[xRoot] = yRoot
	} else if rank[xRoot] > rank[yRoot] {
		parent[yRoot] = xRoot
	} else {
		parent[yRoot] = xRoot
		rank[xRoot]++
	}
}
func kruskal(graph []Edge, nVertices int) []Edge {
	result := make([]Edge, 0)
	parent := make([]int, nVertices)
	rank := make([]int, nVertices)
	for i := 0; i < nVertices; i++ {
		parent[i] = i
		rank[i] = 0
	}
	for _, edge := range graph {
		x := find(parent, edge.u)
		y := find(parent, edge.v)
        // 如果边 (x,y) 不属于原来的最小生成树 T，则加入结果集中，并合并两个顶点所在的集合
        if x != y {  
            result = append(result, edge)
            union(parent, rank, x, y)
        }
    }
    return result
}
func main() {
	graph := []Edge{
        {0 ,1 ,4},
        {0 ,7 ,8},
        {1 ,2 ,8},
        {1 ,7 ,11},
        {2 ,3 ,7},
        {2 ,8 ,2},
        {2 ,5, 4},
        {3, 4, 9},
        {3, 5, 14},
        {4, 5, 10},
        {5, 6, 2},
        {6, 7, 1},
        {6, 8, 6},
        {7, 8, 7},
    }
    
    n := len(graph)
    T := kruskal(graph, n)
    
    fmt.Println("原来的最小生成树：")
    for _, edge := range T {
    	fmt.Printf("(%d,%d) weight:%d\n", edge.u, edge.v, edge.weight)
    }
    
    // 假设减小了边 (0，1) 的权重
    x := Edge{0 ,1 ,4}
    k := 2
    
    wPrime := func(u int,v int) int {
    	if u == x.u && v == x.v {
    		return x.weight - k
    	}
    	return graph[u].weight
    }
    
    fmt.Println("新的最小生成树：")
    
	for i := range T {
	    if T[i] == x {
	    	T[i].weight = x.weight - k
	    	break
	    }
	}
	
	for _, edge := range T {
		fmt.Printf("(%d,%d) weight:%d\n", edge.u, edge.v, edge.weight)
	}
}