F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 1016 >> 证一证可能用到的几个定理(不含解法)
Sengxian @ 2016-08-22 20:19:05
[ Quote ] [ Edit ] [ Delete ] 1#
**定理一:**如果 $A, B$ 同为 $G$ 的最小生成树,且 $A$ 的边权从小到大为 $w(a_1), w(a_2), w(a_3), \cdots w(a_n)$,$B$ 的边权从小到大为 $w(b_1), w(b_2), w(b_3), \cdots w(b_n)$,则有 $w(a_i) = w(b_i)$。
**证明:**设 $A, B$ 第一个不同的边的下标为 $i$,不妨设 $w(a_i) \le w(b_i)$,如果不存在这样的 $i$,无需证明。
情况一:$a_i$ 在 $B$ 中,为 $b_j$。那么显然有 $j>i$(否则 $i$ 不是第一个不同的边),则有 $w(a_i)\le w(b_i) \le w(b_j) = w(a_i)$,所以有 $w(a_i) = w(b_i) = w(b_j)$,所以可以调换 $b_i, b_j$ 的位置,$B$ 的权值排列不会改变, $A$ 与 $B$ 这样前 $i$ 条边均为相等,可以递归下去证明。
情况二:$a_i$ 不在 $B$ 中。考虑将 $a_i$ 加入 $B$,则形成了一个环,环中的权值 $v\le w(a_i)$(否则 $B$ 不是最小生成树),且一定有一条边 $b_j$ 不在 $B$ 中,此时仍有 $j>i$(否则 $i$ 不是第一个不同的边),所以有 $w(a_i)\le w(b_i) \le w(b_j) \le w(a_i)$,所以仍有 $w(a_i) = w(b_i) = w(b_j)$,可以将 $b_j$ 替换为 $a_i$,$B$ 的权值排列不会改变且仍为最小生成树,仍然调换 $b_i, b_j$ 的位置,$B$ 的权值排列仍会改变,这样 $A$ 与 $B$ 前 $i$ 条边均为相等,可以递归下去证明。这样换边不会有问题,因为 Kruskal 算法中唯一的状态就是连通性,我们没有改变其连通性,所以是可以递归证明的。

**定理二:**如果 $A, B$ 同为 $G$ 的最小生成树,如果 $A, B$ 都从零开始从小到大加边($A$ 加 $A$ 的边,$B$ 加 $B$ 的边)的话,每种权值加完后图的联通性相同。
**证明:**归纳法证明,没有边时显然成立,假设对于权值小于 $v$ 的成立。考虑权值为 $v$ 的边,如果连通性不相同,必然存在 $u, v$ 两点间连通性不同,假设 $A$ 中 $u, v$ 联通,根据 $A, B$ 所有小于 $v$ 的边连通性相同,所以必然存在一条 $u\rightarrow v$ 权值为 $v$ 的边,而根据 Kruskal 算法的执行过程, $B$ 不可能不加这条边,所以两棵最小生成树 $A, B$ 各自权值小于等于 $v$ 的边仍然满足连通性相同。由归纳法可知定理二成立。

**定理三:**如果在最小生成树 $A$ 中权值为 $v$ 的边有 $k$ 条,用任意 $k$ 条权值为 $v$ 的边替换 $A$ 中的权为 $v$ 的边且**不产生环**的方案都是一棵合法最小生成树。
**证明:**根据之前的定理,其余的边造成的连通性是定的,权值和也是定的,那么选 $k$ 条不产生环一定能形成一棵树,而且权值与最小生成树的权值一样,故也是最小生成树。

解法:https://blog.sengxian.com/solutions/bzoj-1016
lsy263 @ 2019-07-27 22:35:26
[ Quote ] [ Edit ] [ Delete ] 2#
望丰展?使MK
[Top] [Previous Page] [Next Page]

HOME Back