Mengzelev's Blog

图论学习笔记-图中的连通性与距离

Word count: 1,269 / Reading time: 5 min
2018/11/14 Share

割点

割点的定义:去掉这个点后,原图不再连通

定理5.1:设$v$是连通图$G$中与bridge相连的一个结点,则$v$是割点当且仅当$deg v\ge 2$
非简单树 = 端点 + 割点

推论5.2:设$G$是一个至少有3个顶点的连通图,若$G$有bridge,则$G$一定有割点

定理5.3:设$v$是连通图$G$的一个割点,$u$和$w$是$G-v$不同components中的两个顶点,则$v$位于$G$的任意一条$u-w$路径上。

回顾定理4.1:边$e$是bridge当且仅当$e$不存在于任何一个cycle上

推论5.4:$v$是连通图$G$的一个割点 当且仅当 存在与$v$不同的两个顶点$u$和$w$,使得$v$位于$G$的任意一条$u-w$路上

定理5.5:设$G$是非平凡连通图,$u\in V(G)$。若$v$是$G$中距离$u$最远的顶点,则$v$不是$G$的割点。

推论5.6:任意非平凡的连通图至少包含两个非割点的顶点。

块(Blocks)

不可分图(nonseparable graph):没有割点的非平凡连通图

定理5.7:结点数不少于3的图是不可分的 当且仅当 任意两个顶点都位于某个圈上

块(block):图$G$的一个最大的不可分子图

定理5.8:$R$是定义在非平凡连通图$G$的边集上的关系:对于$e,f\in E(G)$,若$e=f$或$e,f$位于$G$的同一个圈上,则$e,f$有关系$R$,即为$eRf$且$R$是等价关系。
该定理将图$G$的边画划分为了若干等价类。

推论5.9:非平凡连通图$G$的任意两个不同的块$B_1$和$B_2$具有下面性质:

  • $B_1$和$B_2$是不相交的
  • $B_1$和$B_2$至多有一个公共结点
  • 若$B_1$和$B_2$有一个公共结点$v$,则$v$是$G$的割点

连通度

顶点割

顶点割(vertex-cut):顶点集$U$,$G-U$是不连通的

最小顶点割:自行感受一下

只有非完全图才有顶点割,且所有非完全图都有顶点割

(点)连通度(vertex-connectivity):$\kappa(G)$=最小顶点割的基数
$$ 0\le \kappa(G)\le n-1 $$

图$G$是k-连通的(k-connected),即$\kappa(G)\ge k$,随便去掉$k$个点之后依然是连通的

边割(edge-cut)

边割(edge-cut):边集$X$,$G-X$是不连通的

最小边割极小边割是不同的概念

边连通度(edge-connectivity):$\lambda(G)$=最小边割的基数
$$ 0\le \lambda(G)\le n-1 $$

完全图的边连通度$\lambda(K_n)=n-1$

点、边连通度间的关系

定理5.11:对于任意图$G$,$$\kappa(G)\le \lambda(G)\le \delta(G)$$
点连通度$\le$边连通度$\le$最小度数

定理5.12:立方图$\kappa(G)=\lambda(G)$

定理5.13:$G$顶点数为$n$,边数为$m$,则$\kappa(G)\le \lfloor\frac{2m}{n}\rfloor$

Harary图

定理5.14:如果$G$是至少有3个结点的连通图,则$G^2$时候2-连通的。

定理5.15:对于任意整数$r,n$满足$2\le r<n$,有$$\kappa(H_{r,n})=r$

Menger定理

分离集(separating set):$S$是图$G$的顶点集的一个子集,$u$和$v$是$G$的两个顶点。若$G-S$是不连通的且$u$和$v$属于$G-S$不同的连通分支,则称$S$分离$u$和$v$,$S$是一个$u-v$分离集

内点(internal vertex):一条$u-v$路径上除去$u,v$的点
内部不相交(internally disjoint):两条路径除端点外没有公共点

定理5.16(Menger定理):设$u$和$v$是图$G$的不邻接的两个顶点,则$u-v$分离集中顶点的最小个数等于$G$中内部不相交$u-v$路的最大个数。
证明使用了数学归纳法,归纳步时分了3种情况讨论

定理5.17:一个非平凡图$G$是$k$连通的($k\ge 2$) 当且仅当 对于$G$的任意两个顶点$u,v$,$G$至少有$k$条内部内部不相交的$u-v$路。

推论5.18:设$G$为$k$连通图,$S$是由$G$中任意$k$个顶点构成的集合。若图$H$是由$G$通过添加一个新的顶点$w$以及连接$w$到$S$中所有的顶点所得,则$H$也是$k$连通的。

推论5.19:若$G$为$k$连通图,$u,v_1,v_2,…,v_k$为$G$中$k+1$个不同的顶点,则$G$有内部不相交的$u-v_i$路($1\le i\le k$)

定理5.20:若$G$为$k$连通图($k\ge 2$),则$G$中任意$k$个顶点均位于某一个圈上。

定理5.21:对于图$G$两个不同的顶点$u$和$v$,$G$中分离$u,v$的边的最小个额数等于$G$中边不相交$u-v$路的最大个数

定理5.22:一个非平凡图$G$是$k$边连通的当且仅当对于$G$中任意两个不同的顶点$u,v$,$G$包含$k$条边不相交的$u-v$路

CATALOG
  1. 1. 割点
  2. 2. 块(Blocks)
  3. 3. 连通度
    1. 3.1. 顶点割
    2. 3.2. 边割(edge-cut)
    3. 3.3. 点、边连通度间的关系
    4. 3.4. Harary图
  4. 4. Menger定理