第三章 图的连通性

研究图的连通性的意义

研究图的连通性, 主要是对图的连通程度进行刻画. 本章将用图的 (边) 连通度来衡量图的连通程度.

实际意义: 图的连通程度的高低, 对应于通信网络“可靠性程度”的高低 (好的网络不易使其中断).

可靠性参数

网络可靠性, 是用可靠性参数来描述的. 主要分确定性参数与概率性参数.

• 概率性参数主要考虑网络中的处理器或(与)连线以随机的、独立的概率p损坏的情形下, 网络是否仍然连通.
• 确定性参数主要考虑网络在最坏情况下(网络发生最多的元件故障)的可靠性度量, 通常用图论方法给出.

其中, 本章将介绍的图的连通度就是网络的确定性参数. 近年来, 人们又提出了“条件连通度”和“坚韧度”等描述网络可靠性的参数.

3.1 ★割边,割点和块

割边及其性质

割边

边 $e$ 为图 $G$ 的一条割边 (cut edge) 或桥 (bridge), 如果 $\omega (G-e)>\omega (G)$.

注: 删去一条割边后, 图的连通分支数恰好增大 $1$.

定理1

边 $e$ 是图 $G$ 的割边当且仅当 $e$ 不在 $G$ 的任何圈中.

证明: 可以假设 $G$ 连通.

必要性 (边 $e$ 是图 $G$ 的割边 => $e$ 不在 $G$ 的任何圈中)
若不然. 设 $e$ 在图 $G$ 的某圈 $C$ 中, 且令 $e=uv$. 考虑 $P=C-e$, 则 $P$ 是一条 $uv$ 路. 下面证明 $G-e$ 连通.
对任意 $x,y\in V(G-e)$, 由于 $G$ 连通, 所以存在 $x\cdots y$ 路 $Q$.

• 若 $Q$ 不包含 $e$, 则 $x$ 与 $y$ 在 $G-e$ 里连通;
• 若 $Q$ 包含有 $e$, 则可选择路: $x\cdots uPv\cdots y$, 说明 $x$ 与 $y$ 在 $G-e$ 里也连通.

所以, 若边 $e$ 在 $G$ 的某圈中, 则 $G-e$ 连通. 但这与 $e$ 是 $G$ 的割边矛盾！

充分性 ($e$ 不在 $G$ 的任何圈中 => 边 $e$ 是图 $G$ 的割边)
若不然. 假设 $e$ 不是 $G$ 的割边, 则 $G-e$ 连通, 于是在 $G-e$ 中存在一条 $u\cdots v$ 路, 显然: 该路并上边 $e$ 得到 $G$ 中一个包含边 $e$ 的圈, 矛盾.

推论

$e$ 为连通图 $G$ 的一条边, 如果 $e$ 含于 $G$ 的某圈中, 则 $G-e$ 连通.

证明: 若不然, $G-e$ 不连通, 于是 $e$ 是割边. 由定理1, $e$ 不在 $G$ 的任意圈中, 矛盾！

注: 这就是破圈法删边时保持图连通的原因.

例

求证:

(1) 若 $G$ 的每个顶点的度数均为偶数, 则 $G$ 没有割边;
(2) 若 $G$ 为 $k$ 正则二部图 ($k\ge 2$), 则 $G$ 无割边.

证明:

(1) 若不然, 设 $e=uv$ 为 $G$ 的割边, $G-e$ 不连通. 则 $G-e$ 的含有顶点 $u$ (或 $v$) 的那个分支中点 $u$ (或 $v$) 的度数为奇, 而其余点的度数为偶数, 与握手定理推论相矛盾！

(2) 若不然, 设 $e=uv$ 为 $G$ 的割边, $G-e$ 不连通. 取 $G-e$ 的其中一个分支 $G_1$, 显然, $G_1$ 中只有一个顶点的度数是 $k-1$, 其余点的度数为 $k$.
并且 $G_1$ 仍然为二部图. 若 $G_1$ 的两个顶点子集包含的顶点数分别为 $m$ 与 $n$, 并且包含 $m$ 个顶点的顶点子集包含度为 $k-1$ 的那个点, 那么有: $km-1=kn$. 但是因 $k\ge 2$ , 所以等式不能成立！

割点及其性质

分离点

在 $G$ 中, 如果 $E(G)$ 可以划分为两个非空子集 $E_1$ 与 $E_2$, 使 $G[E_1]$ 和 $G[E_2]$ 以点 $v$ 为唯一的公共顶点, 称 $v$ 为 $G$ 的一个分离点 (separating vertex).

割点

称 $v$ 是图 $G$ 的割点 (cut vertex) 如果满足 $\omega (G-v)>\omega (G)$.

定理2

$G$ 无环且非平凡, 则 $v$ 是 $G$ 的分离点, 当且仅当 $\omega (G-v)>\omega (G)$.

证明:
设 $v$ 是 $G$ 的分离点. 则 $E(G)$ 可划分为两个非空边子集 $E_1$ 与 $E_2$, 使 $G[E_1]$, $G[E_2]$ 恰好以 $v$ 为公共点.
由于 $G$ 没有自环, 所以, $G[E_1]$, $G[E_2]$ 分别至少包含异于 $v$ 的 $G$ 的点, 这样, $G-v$ 的分支数比 $G$ 的分支数至少多 $1$, 所以: $\omega (G-v)>\omega (G)$.

注:
(1) 当图无自环 (loop) 时, 分离点就是割点.
(2) 删去一个割点后, 图的连通分支数至少增大 $1$. (分别考虑 $P_m$ 和 $K_{1,m},m\ge 3$) .

定理3

$v$ 是树 $T$ 的顶点, 则 $v$ 是割点, 当且仅当 $v$ 是树的分支点.

证明:

“必要性”
若不然, 有 $d(v)=1$, 即 $v$ 是树叶, 显然不能是割点.

“充分性”
设 $v$ 是分支点, 则 $d(v)>1$.于是设 $x$ 与 $y$ 是 $v$ 的邻点, 由树的性质, 只有唯一路连接 $x$ 与 $y$, 所以 $G-v$ 分离 $x$ 与 $y$, 即 $v$ 为割点.

定理4

设 $v$ 是简单连通图 $G$ 的一个顶点, 则 $v$ 是 $G$ 的割点, 当且仅当 $V(G-v)$ 可以划分为两个非空子集 $V_1$ 与 $V_2$, 使得对任意 $x\in V_1,y\in V_2$, 点 $v$ 在每一条 $x,y$ 路上.

证明:

“必要性”
$v$ 是简单连通图 $G$ 的割点, 由定理2, $G-v$ 至少有两个连通分支. 设其中一个分支的顶点集为 $V_1$, 另一个分支的顶点集为 $V_2$.
对于任意的 $x\in V_1,y\in V_2$, 在 $G-v$ 中的 $x$ 与 $y$ 不连通, 而在 $G$ 中存在一条 $x,y$ 路上, 那么, 该路必然过 $v$.

“充分性”
若 $v$ 不是图 $G$ 的割点, 那么 $G-v$ 连通, 因此在 $G-v$ 中存在 $x,y$ 路, 当然也是 $G$ 中一条没有经过点 $v$ 的 $x,y$ 路. 矛盾.

注:

• (1) 上述定理表明, 若图代表一个通讯网络, 则割点对应网络的枢纽结点. 若枢纽结点发生了故障, 则整个网络会瘫痪. 因此要能找到割点, 并对割点增强可靠性, 以减弱网络的脆弱性(vulnerability).

• (2) 1972年, Robert Tarjan, 给出了用深度优先搜索的算法(边数的线性时间)找图割点和块, R. Tarjan, Depth-first search and linear graph algorthims, SIAM J. Discrete Math. 1 (1972) 146-160.

• (3) 当一个图的规模较小时, 可以用定义的方式判断是否连通. 然而当规模较大的时候, Tarjan (1972) 给出的深度优先算法通过生成一个搜索树(是生成树)而判断一个图是否连通.

例

求证: 非平凡简单连通图至少有两个非割点.

证明: 由于 $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(G-v)$,

• 若 $x,y$ 在 $G-v$ 的同一分支中, 令 $u$ 是与 $x,y$ 处于不同分支的点, 那么, 通过 $u$, 可说明, $x$ 与 $y$ 在 $G-v$ 的补图中连通.
• 若 $x,y$ 在 $G-v$ 的不同分支中, 则它们在 $G-v$ 的补图中邻接.

所以, 若 $v$ 是 $G$ 的割点, 则 $v$ 不是其补图的割点.

块及其性质

块

没有分离点的连通图称为是一个块 (block);

$G$ 的一个子图 $B$ 称为是 $G$ 的一个块, 如果:

• (1) 它本身是块, 即是无分离点的连通图;
• (2) 若没有真包含 $B$ 的块存在 (极大子图).

定理5

设 $G$ 是简单图, 若 $|V(G)|\ge 3$, 则 $G$ 是块当且仅当 $G$ 的任意两个顶点位于同一圈上.

证明:

(必要性)

设 $G$ 是块. 显然 $G$ 没有割点 (简单图无自环) 且 $|V(G)|\ge 3$ , 对任意 $u,v\in V(G)$, 下面证明 $u,v$ 位于某一圈上.

对 $d(u,v)$ 作数学归纳法证明.

当 $d(u,v)=1$ 时, 由于 $G$ 是至少 $3$ 个点的块, 所以, 边 $uv$ 不能为割边, 否则, $u$ 或 $v$ 为割点, 矛盾. 由割边性质, $uv$ 必然在某圈中.

设当 $d(u,v)<k$ 时结论成立. 设 $d(u,v)=k$.
设 $P$ 是一条最短 $u,v$ 路, $w$ 是 $v$ 前面一点, 则 $d(u,w)=k-1$.
由归纳假设, $u$ 与 $w$ 在同一圈 $C=P_1\cup P_2$ 上.

考虑 $G-w$. 由于 $G$ 是块, 所以 $G-w$ 连通. 设 $Q$ 是一条在 $G-w$ 中的 $u,v$ 路, 并且设它与 $C$ 的最后一个交点为 $x$.

则 $u{P}_{1}xvw{P}_{2}u$ 为包含 $u,v$ 的圈.

(充分性) 用反证法. 若 $G$ 不是块, 则 $G$ 中有割点 $v$, 所以 $G-v$ 至少两个分支. 设 $x,y$ 是 $G-v$ 的两个不同分支中的点, 则 $x,y$ 在 $G$ 中不能位于同一圈上, 矛盾！

定理6

点 $v$ 是简单图 $G$ 的割点当且仅当 $v$ 属于 $G$ 的至少两个不同的块.

证明:

(必要性)
设 $v$ 是 $G$ 的割点. 由割点定义: $E(G)$ 可以划分为两个边子集 $E_1$ 与 $E_2$. 显然 $G[E_1]$ 与 $G[E_2]$ 有唯一公共顶点 $v$. 设 $B_1$ 与 $B_2$ 分别是 $G[E_1]$ 和 $G[E_2]$ 中包含 $v$ 的块, 显然它们也是 $G$ 的块. 即证明 $v$ 至少属于 $G$ 的两个不同块.

(充分性)
如果 $v$ 属于 $G$ 的两个不同块, 我们证明: $v$ 一定是图 $G$ 的割点.
设包含 $v$ 的两个块是 $B_1$ 与 $B_2$. 那么两个块分别至少有两个顶点. 假如 $v$ 不是割点, 在 $B_1$ 与 $B_2$ 中分别找异于 $v$ 的一个点 $x$ 与 $y$, $x\in V(B_1),y\in V(B_2)$, 则在 $G-v$ 中有连接 $x$ 与 $y$ 的路 $P$. 则 $B_1\cup B_2$ 无割点, 这与 $B_1,B_2$ 是块矛盾！

注:

• (1) 该定理揭示了简单图中的块与图中割点的内在联系: 不同块的公共点一定是图的割点.

• (2) 图的块可以按割点进行寻找 (按点索块). 所以, 该定理的意义在于: 可以得到寻找图中全部块的算法 (可通过深度优先算法 DFS 得到).

块割点树 $B(G)$

为了直观反映图的块和割点(非简单图为分离点)之间的联系, 引进所谓的块割点树.

设 $G$ 是非平凡连通图. $B_1,B_2,\dots ,B_k$ 是 $G$ 的全部块, 而 $v_1,v_2,\dots ,v_t$ 是 $G$ 的全部割点 (非简单图为分离点). 构造 $G$ 的块割点树 (block cut-vertex tree) $B(G)$: 它的顶点是 $G$ 的块和割点, 连线只在块割点之间进行, 一个块和一个割点连线, 当且仅当该割点是该块的一个顶点.

3.2 ★连通度

点连通度与边连通度的概念

点割 边割

给定连通图 $G$, 设 $V^{\prime }\subseteq V(G)$, 若 $G-V^{\prime }$ 不连通, 称 $V^{\prime }$ 为 $G$ 的一个 (顶) 点割 (vertex cut); 包含 $k$ 个顶点的点割称为 $k$ 点割 ($k$-cut). $G$ 中点数最少的点割称为最小点割 (minimum vertex cut).

给定连通图 $G$, 设 $E^{\prime }\subseteq E(G)$, 若 $G-E^{\prime }$ 不连通, 则称 $E^{\prime }$ 为 $G$ 的一个边割 (edge cut); 包含 $k$ 条边的边割称为 $k$ 边割 ($k$-edge cut). $G$ 中包含边数最少的边割称为最小边割 (minimum edge cut).

• $G_1$中: $\{v_3\},\{v_3,v_5\},\{v_4,v_5\}$等都是点割. $G_2$ 没有点割.

• $G_1$中: $\{v_1{v}_2,v_1{v}_3\},\{v_3{v}_5,v_3{v}_4\}$都是边割. $G_2$ 中 $v_1$ 的所有关联边构成一个最小边割.

(点) 连通度 $\kappa$

在 $G$ 中, 若存在点割, 则称 $G$ 的最小点割的顶点数为 $G$ 的 (点) 连通度 (connectivity), 记为 $\kappa (G)$, 简记为 $\kappa$; 否则称 $n-1$ 为其点连通度 (无点割, 使得剩余图为孤立点时需删去的顶点数). 若 $G$ 不连通, 则 $\kappa (G)=0$.

• $G_1$ 的点连通度 $\kappa (G_1)=1$;

• $G_2$ 的点连通度为 $\kappa (G_2)=n-1=3$;

• $G_3$ 的点连通度为 $\kappa (G_3)=0$.

注:

1. (边)连通度在芯片和集成电路设计, 通讯网络的可靠性, 交通规划, 聚类分析等方面都有应用;
2. 计算图的连通度有多项式时间算法, 可参考文献doi:10. 10.1109/SFCS.1996.548505

边连通度 $\lambda$

在 $G$ 中, 最小边割所含边数称为 $G$ 的边连通度 (edge-connectivity). 边连通度记为 $\lambda (G)$.若 $G$ 不连通或 $G$ 是平凡图, 则定义 $\lambda (G)=0$.

• $G_1$ 的边连通度为 $\lambda (G_1)=1$;

• $G_2$ 的边连通度为 $\lambda (G_2)=3$;

• $G_3$ 的边连通度为 $\lambda (G_3)=0$.

注:

(1) 连通度的概念是1932年由Whitney首先提出并研究, 但他未给出边连通度的定义; κ, λ的记号是由Harary1962年给出.

(2) 计算图的边连通度也有多项式时间算法(M. Stoer, F. Wagner, A simple min-cut algorithm, J. ACM 44 (1997) 585-591).

$k$ 连通, $k$ 边连通

在 $G$ 中, 若 $\kappa (G)\ge k$, 称 $G$ 是 $k$ 连通的 ($k$-connected); 若 $\lambda (G)\ge k$,称 $G$ 是 $k$ 边连通的 ($k$-edge-connected).

例如：

是连通的, 1连通的, 2连通的, 3连通的, 同时也是1边连通的, 2边连通的, 3边连通的. 但不是4连通的.

(大的可以推出小的)

如何确定 $G$ 是否 $k$ (边) 连通? 验证 $\kappa \ge k(\lambda \ge k)$, 一般是找是否存在一个点(边)割 $<k$ 个点(条边) [否定].

例

$\kappa (C_n)=2$, 其中 $C_n$ 表示 $n$ 长圈 ($n\ge 3$).

例

求证: 对图 $G$ 的任意一个顶点 $v$ 和一条边 $e$, 有如下关系式:

• (1) $\kappa (G)-1\le \kappa (G-v)$;

• (2) $\lambda (G)-1\le \lambda (G-e)\le \lambda (G)$;

• (3) $\kappa (G)-1\le \kappa (G-e)\le \kappa (G)$. (下节课的证明中要用到)

证明:

(1) 若 $G-v$ 无点割, 则 $\kappa (G-v)=(n-1)-1=n-2$; 另一方面, $\kappa (G)\le n-1$, 故结论成立.

若 $G-v$ 存在点割, 则设 $V_{\min }$ 为其最小点割, 即 $|V_{\min }|=\kappa (G-v)$.
注意到 $v\cup V_{\min }$ 是 $G$ 的点割,
那么 $\kappa (G)\le |v\cup V_{\min }|=\kappa (G-v)+1$.

(2),(3)的证明留给大家作为练习.

注:

• (1) 一般地, $\kappa (G-v)\le \kappa (G)$ 不成立. 例如, 一个点发出两条边连向于 $K_n$ 的两个不同顶点构成的图 $(n\ge 4)$.
• (2) $\lambda (G-v)$ 与 $\lambda (G)$ 差值可能很大 (考虑 $K_1\vee 2K_n$);
  而一般地, $\lambda (G)-1\le \lambda (G-v)$ 不成立 (考虑 (1) 中构造的图).

总结:

• (0) 去掉一个点, 边连通度变化可能很大;
• (1) 去掉一个点, 连通度可能增加可能减少, 但至多减少 1;
• (2) 去掉一条边, 边连通度可能减少, 但至多减少 1;
• (3) 去掉一条边, 连通度可能减少, 但至多减少 1.

连通度的性质

定理1: Whitney 定理

(Whitney, 1932) 对任意图 $G$, 有:

$$\kappa (G)\le \lambda (G)\le \delta (G)$$

证明: 仅对连通图 $G$ 证明该结论.

(1) 先证明 $\lambda (G)\le \delta (G)$
最小度顶点的关联边集作成 $G$ 的边割集, 所以: $\lambda (G)\le \delta (G)$.

(2) 再证明 $\kappa (G)\le \lambda (G)$
由定义, $\kappa (G)\le n-1$.考虑最小边割 $[S,\overline{S}]$ (表示一个最小边割中 $S$ 到 $\overline{S}$ 之间的所有边的集合).

情形1: $S$ 中点与 $\overline{S}$ 中点均连接, 则有:

$$\lambda (G)=|[S,\overline{S}]|=|S|\cdot |\overline{S}|\ge n-1\ge \kappa (G)$$

所以有: $\kappa (G)\le \lambda (G)$.

情形2: $S$ 中点与 $\overline{S}$ 中点不全相邻, 在这种情形下, 取 $x\in S,y\in \overline{S}$，且 $x$ 与 $y$ 不相邻.

令: $T=\{v|x\leftrightarrow v,且v\in \overline{S}\}\cup \{u|u\ne x,u\in S,且u在\overline{S}中有邻点\}$

于是, $G$ 中任意一条 $x,y$ 路必然经过 $T$ 中一些点, 所以, $T$ 为 $G$ 的一个点割.

在 $G$ 中取如下边集: $E_1=\{xv|v\in \overline{S}\}\cup \{从T\cap S每个顶点取一条到\overline{S}的边\}$

则: $|E_1|=|T|$

所以: $\lambda (G)=|[S,\overline{S}]|\ge |E_1|=|T|\ge \kappa (G)$

注:

(1) 定理中严格不等式能够成立.

$\kappa (G)=1,\lambda (G)=2,\delta (G)=3$

(2) 定理中等式能够成立.

$\kappa (G)=\lambda (G)=\delta (G)=2$

(3) Chartrand 和 Harary (1968) 通过构图的方式已经证明: 对任意正整数 $0<a\le b\le c$, 都存在图 $G$, 使得: $\kappa (G)=a,\lambda (G)=b,\delta (G)=c$.

定理2

令 $S$ 是图 $G$ 的一个非空顶点集, 则:

$$|[S,\bar{S}]|=\sum _{v\in S}d(v)-2E(G[S])$$

证明: $G[S]$ 中的一条边对 ${\sum }_{v\in S}d(v)$ 贡献 $2$, 而 $[S,\bar{S}]$ 中的边仅贡献 $1$ 次. 由握手定理,

$$\sum _{v\in S}d(v)=|[S,\bar{S}]|+2E(G[S])$$

定理3

设 $G$ 是 $(n,m)$ 连通图, 则: $\kappa (G)\le \lfloor 2m/n\rfloor$.

证明: 由握手定理: $2m={\sum }_{v\in V(G)}d(v)\ge n\delta (G)\ge n\kappa (G)$

所以: $\kappa (G)\le \lfloor 2m/n\rfloor$.

哈拉里通过构图的方式证明了定理3的界是紧的. 即存在一个 $(n,m)$ 图 $G$, 使得: $\kappa (G)\le \lfloor 2m/n\rfloor$.

哈拉里图 $H_{k,n}$

由 Whitney 定理知, 连通度为 $k$ 的图至少包含 $\lceil nk/2\rceil$ 条边. 1962年, 数学家 Harary 构造了边数正好等于 $\lceil nk/2\rceil$ 且连通度是 $k$ 的图 $H_{k,n}$, 称为哈拉里图 (Harary graph).

注: 通讯网络线路昂贵时, 用最少的边使得网络达到可能的最大连通度 (可靠性) 有现实的意义.

(1) $H_{2r,n}$

$$\begin{gathered} V(H)=\{0,1,2,\cdots ,n-1\} \\ E(H)=\{ij|\left|i-j\right|\le r(取模n的加法)\} \end{gathered}$$

亦即每个顶点都与其最近的 $r$ 个顶点连边.

$H_{4,8}$:

(2) $H_{2r+1,n}$ ($n$ 为偶数)

先作 $H_{2r,n}$, 然后对 $0\le i<n/2$, $i$ 与 $i+n/2$ 连线.

首先每个顶点都与其最近的 $r$ 个顶点连边, 然后再加上对角顶点间的连边.

$H_{5,8}$:

(3) $H_{2r+1,n}$ ($n$ 为奇数)

先作 $H_{2r,n}$, 然后对 $0\le i\le (n-1)/2$, $i$ 与 $i+(n-1)/2$ 连线.

注意到 $H_{2r+1,n}$不是正则图.

$H_{5,9}$:

定理4

设 $G$ 是 $(n,m)$ 简单图, 若 $\delta (G)\ge \lfloor n/2\rfloor$, 则 $G$ 连通.

证明: 若 $G$ 不连通, 则 $G$ 至少有两个连通分支, 于是, 至少有一个分支 $H$, 使得 $\delta (H)\le \lfloor n/2\rfloor -1<\lfloor n/2\rfloor$, 这与条件矛盾.

注: 事实上, $\delta (G)\ge (n-1)/2$ 时, 上述结论也正确; 但当 $\delta (G)\ge n/2-1$ 时, 结论不再成立.

定理5

设 $G$ 是 $(n,m)$ 简单图, 若 $\delta (G)\ge \lfloor n/2\rfloor$, 则 $G$ 连通. 进一步地, $\lambda (G)=\delta (G)$.

证明: 若 $\lambda (G)<\delta (G)$. 设 $M$ 是 $G$ 的最小边割, 则$|M|=\lambda (G)$, 且 $G-M$ 恰有两个连通分支 $G_1$ 和 $G_2$. 对 $G_1$ 用握手定理得

$$\delta (G)>\lambda (G)=|M|=\sum d(v)-2|E(G_1)|$$

其中 $\sum$ 是对 $G_1$ 中的所有顶点求和.

而又由 $d(v)\ge \delta (G)$, 和 $2|E(G_1)|\le |V(G_1)|(|V(G_1)|-1)$ 得

$$\delta (G)>|V(G_1)|\delta (G)-|V(G_1)|(|V(G_1)|-1)$$

显然有, $|V(G_1)|>1$.

于是, $|V(G_1)|\ge \delta (G)+1$.

同理, $|V(G_2)|\ge \delta (G)+1$.

注意到, $n=|V(G_1)|+|V(G_2)|\ge 2\delta (G)+2$.

$\delta (G)\le n/2-1<\lfloor n/2\rfloor$. 矛盾.

定理6

设 $G$ 是 $(n,m)$ 简单图, 若对任意正整数 $k$ , 有:

$$\delta (G)\ge \frac{n+k-2}{2}$$

则 $G$ 是 $k$ 连通的.

证明: 任意删去 $k-1$ 个顶点, 记所得之图为 $H$, 则:

$$\delta (H)\ge \delta (G)-(k-1)\ge (n+k-2)/2-k+1=(n-k)/2$$

由于 $\delta (H)$ 是整数, 故:

$$\delta (H)\ge \lceil (n-k)/2\rceil =\lfloor (n-k+1)/2\rfloor$$

由定理5, $H$ 连通 ($H$ 包含 $n-k+1$ 个点), 所以, $G$ 是 $k$ 连通的.

注: 不满足定理6的条件的图 (如, $H_{4,8}$) 也可能是 $k$ 连通的, 亦即定理的条件是充分不必要的.

图的坚韧度

点和边连通度对图的连通性刻画存在明显不足, 例如, 我们观察如下3个图:

容易知道: $k(G_1)=k(G_2)=k(G_3)=1$, $\lambda (G_1)=\lambda (G_2)=\lambda (G_3)=1$.

于是, 从点、边连通度角度不能刻画上面3个图的连通性程度的区别. 很明显: $G_3$ 连通性高于 $G_2$, $G_2$ 高于 $G_1$.

基于此, 1996年, 许进在电子学报发表文章, 论述了用坚韧度来刻画图的连通程度比用连通度更精确.

坚韧度 $t(G)$

用 $C(G)$ 表示图 $G$ 的全体点割构成的集合, 非平凡非完全图的坚韧度 (toughness), 记作 $t(G)$, 定义为:

$$t(G)=\min \left\{\frac{|S|}{\omega (G-S)}|S\in C(G)\right\}$$

坚韧度的概念是 Chvátal 提出来研究图的哈密尔顿问题的一个图参数.

容易算出: $t(G_1)=0.2,t(G_2)=0.25,t(G_3)=0.33$, 于是 $G_3$ 比 $G_2$ 的连通性好, $G_2$ 比 $G_1$ 的连通性好.

V. Chvátal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (3) (1973) 215–228

超连通性与限制连通性

在一个 $n$ 阶 $k$ 连通图 $G$ 中, 从 $n$ 个顶点中选取 $k$ 个点的不同组合为 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ , 而仅有 $n$ 个顶点可能为一个平凡点割, 所有平凡点割的可能性为 $Q_1(n)=n/\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

当 $n$ 较大时, 此概率接近为 $0$, 基于此, Harary提出了限制连通度的概念.

如果顶点子集 $S\subset V(G)$ 有 $G-S$ 不连通并且每个分支包含至少两个顶点, 那么 $S$ 称为 $G$ 的 $2$-限制点割. 如果图的 $2$-限制点割存在, 则是其最小 $2$-限制点割包含的顶点数.

如何准确刻画图的连通性程度, 现在还是一个有待进一步研究的问题.

3.3 Menger 定理

Menger 定理是图的连通性问题的核心结论之一, 它描述了图的连通度与连通图中不同点对间的不相交路的数目之间的关系.

分离集

设 $u$ 与 $v$ 是图 $G$ 的两个不相邻 (不同) 顶点, $S$ 是 $G$ 的一个顶点子集 (边子集), 如果 $u$ 与 $v$ 不在 $G-S$ 的同一分支上, 则称 $S$ 分离 (separate) $u$ 和 $v$, $S$ 为 $u,v$ 分离集.

$\{u_1,u_4\},\{u_1{u}_2,u_1{u}_4,u_4{u}_6\}$ 分离点 $u_2$ 与 $u_6$.

内部不交

图 $G$ 的一族路称为是内部不交 (internally disjoint) 的, 如果它们的内部顶点都不相同.

边不重

图 $G$ 的一族路称为是边不重 (edge-disjoint) 的, 如果它们没有公共边.

★定理 (Menger, 1927)

(1) 设 $x$ 与 $y$ 是图 $G$ 中的两个不相邻点, 则 $G$ 中分离点 $x$ 与 $y$ 的最少点数等于内部不交 (独立的) $x,y$ 路的最大数目;

(2) 设 $x$ 与 $y$ 是图 $G$ 中的两个不同点, 则 $G$ 中分离点 $x$ 与 $y$ 的最少边数等于 $G$ 中边不重的 $x,y$ 路的最大数目.

在该图中, 独立的 $x,y$ 路最大条数是 $2$ (红色和蓝色路); 分离点 $x$ 与 $y$ 的最小分离集是 $u_1,u_2$, 包含两个顶点.

又在该图中, 边不重的 $x,y$ 路最大条数是 $2$ (红色和蓝色路); 分离点 $x$ 与 $y$ 的最小边分离集是 $x{u}_1,x{u}_2$, 包含两条边.

该定理是图论中, 也是通信理论中的最著名的定理之一, 是由奥地利杰出数学家 Menger 在 1927 年发表的.

定理 (Whitney, 1932)

非平凡简单图 $G$ 是 $k(k\ge 2)$ 连通的, 当且仅当 $G$ 的任意两个顶点 $u,v$ 间至少存在 $k$ 条内部不交路.

证明:

(必要性) 设 $G$ 是 $k(k\ge 2)$ 连通的, $u$ 与 $v$ 是 $G$ 的两个顶点.

如果 $u$ 与 $v$ 不相邻, $U$ 为 $G$ 的最小 $u,v$ 分离集, 那么 $|U|\ge \kappa (G)\ge k$, 于是由 Menger 定理, 结论成立;

若 $u$ 与 $v$ 邻接, 其中 $e=uv$ , 那么, 容易证明: $G-e$ 是 $(k-1)$ 连通的. 设 $W$ 是 $G-e$ 的最小 $u,v$ 分离集, 由 Menger 定理知, $G-e$ 至少包含 $k-1$ 条内点不交的 $u,v$ 路, 这与边 $uv$ 一起构成 $G$ 中至少 $k$ 条内部不交的 $u,v$ 路.

(充分性) 若 $G$ 不存在点割, 则 $G$ 是完全图. 显然有 $k=n-1$, 即 $\kappa (G)=n-1$.

设 $U$ 是分离两个不相邻点 $u$ 与 $v$ 的最小点割, 则 $G-U$ 不连通. 已知 $u$ 与 $v$ 之间至少存在 $k$ 条内部不交路, 若 $|U|=\kappa (G)\le k-1$, 则 $G-U$ 中至少至少存在一条 $u,v$ 路, 即 $G-U$ 连通. 这说明 $\kappa (G)\ge k$, 即 $G$ 是 $k$ 连通的.

注: 上述定理是定义完全图 (或以完全图为生成子图) 的连通度为 $n-1$ 的依据 (因完全图中任意两点间都有 $n-1$ 条内部不交路).

扩张引理

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

证明: 首先, 分离 $G$ 中两个不相邻顶点至少要 $k$ 个点, 其次, 分离 $w$ 与 $G$ 中不在 $S$ 中顶点需要 $k$ 个顶点. 因此 $H$ 是 $k$ 连通的.

例

设 $G$ 是 $k$ 连通图, $u,v_1,v_2,\dots ,v_k$ 为 $G$ 中 $k+1$ 个不同顶点. 求证: $G$ 中有 $k$ 条内部不交路 $(u,v_i)(1\le i\le k)$

证明: 在 $G$ 外添加一点 $w$, 让 $w$ 与 $v_i$ 邻接 $(1\le i\le k)$ 得 $H$.

由扩张引理, $H$ 是 $k$ 连通的, 于是由定理 (Whitney, 1932), $u$ 与 $w$ 间存在 $k$ 条内部不交的 $u,w$ 路, 所以 $G$ 中有 $k$ 条内部不交路 $(u,v_i)(1\le i\le k)$.

定理 (Whitney 1932)

对于边连通性, 有类似定理:

一个非平凡的图 $G$ 是 $k(k\ge 2)$ 边连通的, 当且仅当 $G$ 的任意两个顶点间至少存在 $k$ 条边不重的 $(u,v)$ 路.

推论

对于一个阶至少为 $3$ 的无环图 $G$, 下面四个命题等价.

(1) $G$ 连通且无割点;
(2) $G$ 是 $2$ 连通的;
(3) $G$ 中任意两点位于同一个圈上;
(4) $G$ 无孤立点, 且任意两条边在同一个圈上.

注: 阶至少为 $3$ 的简单 $2$ 连通图就是块.

证明:

(1)⟺(2) 3.1 中定理 5 已证.

(2)⟺(3)

$G$ 是 $2$ 连通的当且仅当 $G$ 的任意两个顶点间存在两条内点不交路 $P_1$ 与 $P_2$, 显然这两条路构成包含该两个顶点的圈.

(3)⟹(4)

$G$ 显然无孤立点. 设 $e_1=uv$ 与 $e_2=xy$ 是 $G$ 的任意两条边. 显然 $G$ 是 $2$ 连通的.

在 $e_1$ 和 $e_1$ 的端点上分别添加一个邻点 $w$ 和 $z$ 得到图 $H$. 由扩张引理知, $H$ 仍是 $2$ 连通的, 则 $w$ 与 $z$ 在 $H$ 的一个圈 $C$ 上. 由 $w$ 与 $z$ 是 $H$ 的 $2$ 度点知, 可将 $C$ 修改为过 $e_1$ 和 $e_2$ 的圈.

(4)⟹(3)

设 $u$ 与 $v$ 是无环图 $G$ 的任意两个顶点, 由于 $G$ 无孤立点, 所以可设 $e_1,e_2$ 分别与 $u,v$ 相关联. 由 (4) 知, $e_1,e_2$ 在同一个圈上, 所以 $u$ 与 $v$ 在同一个圈上.