0%

【知识总结】 k-连通图

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定理推论

的图G是k-连通图

G中任二顶点至少被k条两两内部无公共顶点的路所连

一个困惑

的图G是k-连通图

G中任二不相邻的顶点至少被k条两两内部无公共顶点的路所连

是否成立呢?