2-连通图的性质
块
G是块：G是无割点的连通图 H是G的块：H是G中极大无割点连通子图
块的等价定义(G是
- G是2-连通的(块)
- G的任二顶点共圈
- G的任一顶点与任一边共圈
- G的任二边共圈
- 对
及 存在 路含有边 - 对
，存在 路含有顶点 - 对
，存在 路不含有顶点
块的一些其他性质
- 两个块最多只有一个公共顶点
- 两个块没有公共边
- 块是对图的边集的一种划分，等价关系是共圈
- 割点
块的交点 - 块-割点图
块的求法
john Hopcroft和Robert Tarjan提出的经典算法 + 思想：基于一次DFS + 时间复杂度：线性 + 详细内容：可参考《算法导论》
Menger定理
分离集
- x-y分离集(x-y cut)：
中没有 路 - 最小x-y分离集(minmum x-y cut)：势最小的x-y分离集
- x-y分离数：最小x-y分离集的势，记为s(x,y)
- 两两内部无公共顶点的x-y路的最大条数：记作r(x,y)
Menger定理内容
设x,y是图G的两个不相邻的顶点，则s(x,y)=r(x,y)
Menger定理推论
一个困惑
是否成立呢？
