dwjshift's Blog

bzoj3569 DZY Loves Chinese II 正确性证明

| Comments

咦这个blog居然又诈尸了

最近又看到了这个题。当年做的时候大概就是看看题解感觉很有道理写完了就没管了,现在仔细想想发现正确性并不显然,自己yy了半天之后终于会证了。网上也没找到比较严谨的证明,就在这写写吧。wyy把dls的证明写到了UOJ上了

大部分题解只是说,图不连通等价于至少有一条树边及覆盖它的所有非树边都被删掉。这个结论显然不对,比如说一个三元环,删掉它的两个树边也是不连通的。

先说要证的结论:选一个生成树,给每条非树边赋一个随机01向量,树边的权值则为覆盖它的非树边权值的异或和。那么删掉一个边集后图不连通的充要条件是他们权值构成的向量集恒线性相关。

必要性

考虑删掉边集后点能分成两个互不连通的点集`$A,B$`。如果`$A,B$`间仅有一条树边,那就是前面说的那种情况,覆盖这条树边的非树边肯定都被删了。否则取出`$A,B$`间的任意两条树边,在所选生成树上把它们砍掉后肯定长这样

`$A,B1,B2$`是在生成树上砍掉两条红色的树边后得到的连通块,其中`$B1,B2$`都在点集`$B$`内。`$E1,E2,E3$`分别是三个连通块间的非树边集。由于`$A,B$`不连通,`$E2,E3$`的边一定都被砍掉了。那么这两条树边及`$E2,E3$`的异或和为`$(E1\ xor\ E2)\ xor\ (E1\ xor\ E3)\ xor\ E2\ xor\ E3=0$`,因此被删的边集线性相关。

Update
上面的证明是错的,因为删掉两条树边后并不一定能变成上图的情况(或者在生成树上本来就不保证是连通的。。。不过仍然可以用类似的思路证明。
假设删掉边集后整个图分成了两个互不连通的点集。考虑边集中所有跨过了两个点集的边(包括树边和非树边)的异或和。对于一条两端都在同侧的非树边,它的权值显然会被树边计算偶数次;而对于两端在异侧的非树边,它的权值会被树边计算奇数次,再加上它本身算的一次后总共也被算了偶数次。因此这些边的异或和必定为0。

充分性

对于一个xor和恒为0的边集,其中至少会有一条树边,那么在生成树上把该边集内的树边都割掉后可以得到至少两个连通块。考虑把每个连通块都缩成一个点后在生成树上黑白染色。对于两个同色连通块间的非树边,它的权值被两个连通块的路径上的树边计算了偶数次,因此它必然不在边集中;同理异色连通块间的非树边必然在边集中。因此删掉该边集后任意两个异色连通块肯定就无法连通了。

本来还想分析一下错误率的,然而发现太难了不会。。。。(不过至少应该不低于个随机向量线性相关的概率?)如果有人会的话求教。。。。

Comments

comments powered by Disqus