最后更新: 2025-01-22 10:07 查看: 125 次纠错评论(0) 课件开VIP

割点与块

割点与块
下面我们先看一下 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$ 时，一条边也就是一个块。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：连通度与块

下一篇：网络最大流

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