我已经找了很多答案来回答下列问题：
给出了一个连通无向图G=（V，E），其权函数为w:E->R。
T1是G的最小生成树，权重为W1。
向图G添加一个具有W（E）权值的新边（顶点连接G中的两个现有顶点）。
T2是加权为W2的更新图的最小生成树。
证明或反驳每个陈述：
如果W1=W2，则边e处于一个循环中，该循环中每个边的权重最多为w（e）。
w2>=w1-w（e）
如果W2
最佳答案
首先，注意以下几点：
由于G是一个连通图，在两个现有顶点之间增加一个边e将在G中创建一个循环。
声明1：我们有W1=W2自相矛盾假设G中存在一个同时e和边e'的循环由于边w(e') > w(e)和e都在同一个循环中，我们可以删除其中一个边并仍然得到生成树。如果我们删除e'，就会得到e'。由于W2 = W1 - w(e') + w(e)，这意味着w(e') > w(e)，这与premis相矛盾因此，这一说法是正确的。
声明3直接来自上述内容。
语句2是错误的，因为我们可以给出一个反例假设图形W2 < W1带有G = (V, E, w)且边V = {A, B, C}带有E = {e1 = (A, B), e2 = (A, C)}和w(e1) = 10。w(e2) = 11是具有权重的最小生成树。现在添加边G和权重W1 = 21。最小生成树现在由边e = (B, C)和w(e) = 1组成，其权重为e1将这些值插入公式e：W2 = 11，这显然不是真的，从而为索赔提供了反例。
关于algorithm - 最小生成树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37607109/