点双的一些性质P:
对于一个点双的u,v和点p,必定存在u-…-p-…-v的简单路径
p为一条边的时候同理
由此继续推下去
对于一个点双,含有奇环,那么任意两个点的简单路径有偶数和奇数
所以里面的所有边都在奇环上
两点一线的点双的边拿出来就是割边
这些割边形成树,且剩下的边不能连在同一颗树中,它们都在环上
所以如果割边形成了x个连通块
那么在保证全图联通,且无重边自环的情况下,加的边数范围如下
1.x=1[0,0]
2.x>1 [x,2x(x−1)]
相关文章
- 02-29从agc-038D来看点双和边双