最后更新: 2025-01-22 10:07 ● 参与者查看: 20 次纠错分享参与项目词条搜索

割点与块

割点与块
下面我们先看一下 2 －连通图的特征。为此，我们先讨论一下割点。由定义 11.4 可知，有割点的连通图是 1 －连通的，但不是 2 －连通的，反之亦然。割点有如下几个等价条件。

定理 11.2 设 $v$ 是连通图 $G$ 的一个顶点，下列论断是等价的。
（1）$v$ 是 $G$ 的一个割点。
（2）对于顶点 $v$ ，存在两个不同的顶点 $u$ 和 $w$ ，使顶点 $v$ 在每一条从 $u$ 到 $w$ 的路上。
（3）存在 $V-\{v\}$ 的一个分成 $U$ 和 $W$ 的划分，使对任意两顶点 $u \in U$ 和 $w \in W$ ，顶点 $v$ 在每一条从 $u$ 到 $w$ 的路上。

证明：（1）$\Rightarrow(3)$ ：因为 $v$ 是 $G$ 的一个割点，$G-\{v\}$ 是不连通的，它至少有两条分支。设 $U$ 是由其中一个分支中的顶点组成，$W$ 则是由其余顶点组成，形成 $V-\{v\}$ 的一个划分。于是任意两顶点 $u \in U$ 和 $w \in W$ 在 $G-\{v\}$ 的不同分支中。因此 $G$ 中每一条从 $u$ 到 $w$ 的路中包含顶点 $v$ 。
（3）$\Rightarrow(2):(2)$ 是（3）的一个特殊情况，所以立即证得。
（2）$\Rightarrow(1)$ ：若 $v$ 在每一条从 $u$ 到 $w$ 的路上，则在 $G-\{v\}$ 中不能有一条从 $u$ 到 $w$ 的路，因此 $G-\{v\}$ 是不连通的，即 $v$ 是 $G$ 的一个割点。

定义 11.6 （可分图／不可分图）有割点的非平凡连通图称为可分图。没有割点的非平凡连通图称为不可分图。

显然，顶点数 $n \geqslant 3$ 的不可分图是 2 －连通图，又称双连通图，下面的定理给出这种图的等价特征。

定理 11.3 设 $G$ 是顶点数 $n \geqslant 3$ 的连通图，下列论断是等价的。
（1）$G$ 中没有割点。
（2）$G$ 的任意两个顶点在同一条回路上。
（3）$G$ 的任意一个顶点和任意一条边在同一条回路上。
（4）$G$ 的任意两条边在同一条回路上。割点与块

证明：（1）$\Rightarrow(2)$ ：设 $u, v$ 是 $G$ 的任意两点，$d(u, v)$ 是从 $u$ 到 $v$ 的距离。对 $d(u, v)$ 用归纳法证明。当 $d(u, v)=1$ 时，由于 $G$ 中没有割点且 $n \geqslant 3$ ，因而 $G$ 是 2 －连通的，$k(G) \geqslant 2$ 。又由定理 11．1，$k(G) \leqslant \lambda(G) \leqslant \delta(G)$ 。所以 $\lambda(G) \geqslant 2$ 。于是可知 $\{u, v\}$ 不是桥，因此 $G-\{u, v\}$ 仍连通，即从 $u$ 到 $v$ 有一条含有其他顶点的路，与 $\{u, v\}$ 构成一条回路，也即 $u, v$ 在同一回路上。假设 $d(u, v)=k-1$ 时结论成立。当 $d(u, v)=k$ 时，令 $w$ 是 $u$ 到 $v$ 长度 $k$ 的路上 $v$ 的相邻点。因 $d(u, w)=k-1$ ，按归纳假设 $G$ 中有一条包含 $u, w$ 的回路 $C$ 。又因 $G$ 没有割点，所以 $G$－$\{w\}$ 是连通的，且含有一条 $u$ 到 $v$ 的路 $p$ 。设 $x$ 是 $p$ 上与回路 $C$ 相交的最后一个顶点，$x$ 也可能就是 $u$ 。不失一般性，假设 $x \in C$ ，于是 $G$ 中有一条含有 $u$ 和 $v$ 的回路：在 $C$ 上 $u$ 到 $x$ 的一条路，并上 $p$ 上的 $x$ 到 $v$的一条路，并上边 $\{w, v\}$ ，再并上在 $C$ 上 $w$ 到 $u$ 的一条路。
（2）$\Rightarrow(3)$ ：设 $u$ 是任意一个顶点，$\{v, w\}$ 是任一边，由（2）可知，存在包含 $u$ 和 $v$ 的回路 $C$ ，若 $w \in C$ ，则即得证；若 $w \notin C$ ，由（2）$, u, w$ 在同一回路上，那么 $v$ 一定不是割点。所以必存在不含顶点 $v$ 的从 $w$ 到 $u$ 的路 $p$ 。设 $x$ 是 $p$ 与 $C$ 相交的第一个顶点，则 $w$ 到 $x$ 沿 $C$ 经 $u$ 到 $v$ ，最后回到 $w$ 的回路即所要求的回路。
（3）$\Rightarrow(4)$ ：与（2）$\Rightarrow(3)$ 的证明类似。
（4）$\Rightarrow(1)$ ：若 $G$ 中有割点 $v$ ，则存在顶点 $u$ 和 $w$ ，使 $v$ 在每一条 $u$ 到 $w$ 的路上，在该路上边 $\{u, x\}$ 与 $\{w, y\}(x, y$ 可能为 $v)$ 必定不在同一回路上，与（4）假设矛盾。

双连通分支
在 $G$ 的边集 $E$ 上建立如下关系：对于 $E$ 中任意两边 $e_1$ 和 $e_2, e_1$ 和 $e_2$ 有关系当且仅当 $e_1=e_2$ 或者 $e_1$ 和 $e_2$ 在同一回路上。容易验证这个关系是一个等价关系。它把边划分为等价类 $E_1, E_2, \cdots, E_k$ ，使得两条不同的边在同一类中当且仅当这两条边在同一回路上。由 $E_i$ 导出的子图记为 $G_i, 1 \leqslant$ $i \leqslant k$ 。每个子图 $G_i$ 称为 $G$ 的一个块，或称双连通分支。所以对于顶点数 $n \geqslant 3$ 的块，它的任意两边在同一回路上，又由定理 11.3 可知，$n \geqslant 3$ 时，块等价于 2 －连通图，即等价于没有割点的连通图。而 $n=2$ 时，一条边也就是一个块。

上一篇：连通度与块

下一篇：网络最大流

本文对您是否有用？有用 (0) 无用 (0)