第三章 图的连通度
3.1 概念
- 割边：设\(e\)是图\(G\)的一条边，若\(\omega (G-e)>\omega (G)\)，则称\(e\)为\(G\)的割边。（\(\omega\)为连通分支数）
- 边\(e\)是图\(G\)的割边当且仅当\(e\)不在\(G\)的任何圈中
- \(e\)为连通图\(G\)的一条边，如果\(e\)含于\(G\)的某圈中，则\(G-e\)连通
- 割点：如果\(E(G)\)可以划分为两个非空子集\(E_1\)与\(E_2\)，使\(G[E_1]\)和\(G(E_2)\)以点\(v\)为公共顶点，称\(v\)为\(G\)的一个割点
- \(G\)无环且非平凡，则\(v\)是\(G\)的割点，当且仅当\(\omega (G-v)>\omega (G)\)
- 设\(v\)是树\(T\)的顶点，则\(v\)是割点，当且仅当\(v\)是树的分支点
- 设\(v\)是无环连通图\(G\)的一个顶点，则\(v\)是\(G\)的割点，当且仅当\(V(G-v)\)可以划分为两个非空子集\(V_1\)与\(V_2\),使得对任意\(x\in V_1\), \(y\in V_2\), 点\(v\)在每一条\((x,y)\)路上
- 块：没有割点的连通图称为块
- 若\(|V(G)|\geq 3\),则\(G\)是块，当且仅当\(G\)无环且任意两顶点位于同一圈上（证明P48）
- 点\(v\)是图\(G\)的割点当且仅当\(v\)至少属于\(G\)的两个不同的块（证明P49）
- 顶点割（点割）：给定连通图\(G\)，设\(V'\subseteq V(G)\)，若\(G-V'\)不连通，称\(V'\)为\(G\)的一个点割集，含有\(k\)个顶点的点割集称为\(k\)顶点割。\(G\)中点数最少的顶点割称为最小顶点割。
- 点连通度\(\kappa\)：在\(G\)中，若存在顶点割，称\(G\)的最小顶点割的顶点数称为\(G\)的点连通度；否则称\(n-1\)为其点连通度。\(G\)的点连通度记为\(\kappa (G)\), 简记为\(\kappa\)。若\(G\)不连通，\(\kappa (G)=0\)
- 边连通度\(\lambda\)：在\(G\)中，最小边割集所含边数称为\(G\)的边连通度。边连通度记为\(\lambda (G)\) 。若\(G\)不连通或\(G\)是平凡图，则定义\(\lambda (G) =0\)
- 在\(G\)中，若\(\kappa (G)≧k\), 称\(G\)是\(k\)连通的；若\(\lambda (G)≧k\)，称\(G\)是\(k\)边连通的
- （惠特尼）定理：对任意图\(G\)，有\(\kappa (G)\leq \lambda (G)\leq \delta (G)\)
- 设\(G\)是\((n,m)\)连通图，则\(\displaystyle \kappa (G)\leq \lfloor \frac{2m}{n}\rfloor\)
- 敏格尔定理:
- 设\(x\)与\(y\)是图\(G\)中的两个不相邻点，则\(G\)中分离点\(x\)与\(y\)的最小点数等于独立的\((x, y)\)路的最大数目
- 设\(x\)与\(y\)是图\(G\)中的两个不相邻点，则\(G\)中分离点\(x\)与\(y\)的最小边数等于\(G\)中边不重的\((x, y)\)路的最大数目
- 惠特尼
- 一个非平凡的图\(G\)是\(k(k\geq 2)\)连通的，当且仅当\(G\)的任意两个顶点\(u\)与\(v\)间，至少存在\(k\)条内点不交的\((u ,v)\)路
- 一个非平凡的图\(G\)是\(k(k\geq 2)\)边连通的，当且仅当\(G\)的任意两个顶点间至少存在\(k\)条边不重的\((u ,v)\)路
- 推论 对于一个阶至少为3的无环图\(G\)，下面三个命题等价：
- \(G\)是2连通的
- \(G\)中任意两点位于同一个圈上
- \(G\)无孤立点，且任意两条边在同一个圈上
证明题：
- 求证：无环非平凡连通图至少有两个非割点
- 证明： 由于\(G\)是无环非平凡连通图，所以存在非平凡生成树，而非平凡生成树至少两片树叶，它不能为割点，所以，它也不能为\(G\)的割点
- 求证：恰有两个非割点的连通单图是一条路
- 证明：设\(T\)是\(G\)的一棵生成树。由于\(G\)有\(n-2\)个割点，所以，\(T\)有\(n-2\)个割点，即\(T\)只有两片树叶，所以\(T\)是一条路。这说明，\(G\)的任意生成树为路。一个单图的任意生成树为路，则该图为圈或路，若为圈，则\(G\)没有割点，矛盾，所以，\(G\)为路
- 求证：若\(v\)是单图\(G\)的割点，则它不是\(G\)的补图的割点
- \(v\)是单图\(G\)的割点，则\(G-v\)至少两个连通分支。现任取\(x,y\in V(\bar{G} -v)\)，如果\(x, y\)在\(G-v\)的同一分支中，令\(u\)是与\(x, y\)处于不同分支的点，那么通过\(u\)，可说明，\(x\)与\(y\)在\(G-v\)的补图中连通。若\(x, y\)在\(G-v\)的不同分支中，则它们在\(G-v\)的补图中邻接。所以，若\(v\)是\(G\)的割点，则v不是其补图的割点
