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

连通度与块

点连通度与边连通度
为了衡量一个图的连通程度，我们要定义图的点连通度与边连通度。
定义 11.1 （点割／割点）设图 $G$ 的顶点子集 $V^{\prime}, \omega\left(G-V^{\prime}\right)>\omega(G)$ ，称 $V^{\prime}$ 为 $G$ 的一个点割。 $\left|V^{\prime}\right|=1$ 时，$V^{\prime}$ 中的顶点称为割点。
 ![图片](/uploads/2025-01/659c1d.jpg)
如在图 11.1 所示的图中，$\left\{v_1, v_4\right\}$ 是点割，$v_5$ 和 $v_6$ 是割点。

定义 11.2 （点连通度／连通度）设有图 $G$ ，为产生一个不连通图或平凡图需要从 $G$ 中删去的最少顶点数称为 $G$ 的点连通度，记为 $k(G)$ ，简称为 $G$ 的连通度。

图 11.1

显然，$G$ 是不连通图或平凡图时，$k(G)=0$ ；连通图 $G$ 有割点时，$k(G)=1 ; ~ G$ 是完全图 $K_n$ 时， $k\left(K_n\right)=n-1$ 。

在图 11.1 所示的图中，$k(G)=1$ 。

定义 11.3 （边连通度）设有图 $G$ ，为产生一个不连通图或平凡图需要从 $G$ 中删去的最少边数称为 $G$ 的边连通度，记为 $\lambda(G)$ 。

显然，$G$ 是不连通图或平凡图时，$\lambda(G)=0$ ；连通图 $G$ 有一桥时，$\lambda(G)=1 ; ~ G$ 是完全图 $K_n$ 时， $\lambda\left(K_n\right)=n-1$ 。

如在图 11.1 所示的图中，$\lambda(G)=1, e_7$ 和 $e_8$ 是桥。
点连通度，边连通度与最小顶点度数的关系由定理 11.1 给出。
定理 11.1 对任何一个图 $G, k(G) \leqslant \lambda(G) \leqslant \delta(G)$ 。
证明：首先证明 $\lambda(G) \leqslant \delta(G)$ 。若 $G$ 没有边，则 $\lambda(G)=\delta(G)=0$ ；否则，必存在顶点 $v$ ， $d(v)=\delta(G)$ 。删除 $v$ 的所有关联边，得到的图必定不连通，所以 $\lambda(G) \leqslant \delta(G)$ 。

下面证明 $k(G) \leqslant \lambda(G)$ 。若 $G$ 是不连通图或平凡图，则 $k(G)=\lambda(G)=0$ 。若 $G$ 是连通图，取断集 $E^{\prime}=E\left(V_1 \times \bar{V}_1\right),\left|E^{\prime}\right|=\lambda(G)$ ，记 $E^{\prime}$ 关联于 $V_1$ 中的点集为 $V^{\prime}$ ，关联于 $\bar{V}_1$ 中的点集为 $V^{\prime \prime}$ ，下面分三种情况分析证明。
（1）$V_1-V^{\prime}$ 或 $\bar{V}_1-V^{\prime \prime}$ 中至少有一个非空。不失一般性，设 $V_1-V^{\prime} \neq \varnothing$ ，则 $G-V^{\prime}$ 不连通，于
是有 $k(G) \leqslant\left|V^{\prime}\right| \leqslant\left|E^{\prime}\right|=\lambda(G)$ 成立。
（2）$V_1-V^{\prime}=\overline{V_1}-V^{\prime \prime}=\varnothing$ ，但 $\min \left(\left|V_1\right|,\left|\bar{V}_1\right|\right)=1$ ，不失一般性，设 $\left|\overline{V_1}\right|=1$ ，则 $G^{-} V_1$ 为平凡图。于是有 $k(G) \leqslant\left|V_1\right| \leqslant\left|E^{\prime}\right|=\lambda(G)$ 成立。
（3）$V_1-V^{\prime}=\overline{V_1}-V^{\prime \prime}=\varnothing$ ，但 $\min \left(\left|V_1\right|,\left|\overline{V_1}\right|\right)>1$ ，则从 $V_1$ 和 $\overline{V_1}$ 中各取若干与 $E^{\prime}$ 中边关联的顶点，这些顶点构成子集 $V_2$ ，且使得 $V_1-V_2 \neq \varnothing, \bar{V}_1-V_2 \neq \varnothing, V_2$ 中顶点关联 $E^{\prime}$ 中全部边，$\left|V_2\right|$ $\leqslant\left|E^{\prime}\right|$ ，那么 $G^{-} V_2$ 不连通。于是 $k(G) \leqslant\left|V_2\right| \leqslant\left|E^{\prime}\right|=\lambda(G)$ 成立。 $V_2$ 的取法如下。任取 $v \in V_1$ ，使 $V_2=\left(V_1-\{v\}\right) \cup\left\{v^{\prime} \mid v^{\prime}\right.$ 关联 $v$ 且 $\left.v^{\prime} \in \bar{V}_1\right\}$ ，易知 $V_2$ 中的每个点都关联 $E^{\prime}$ 中一条边，且这些边是互不相同的。

例11．1 设 $G$ 是有 $n$ 个顶点的简单图，且 $\delta \geqslant n-2$ ，证明 $k(G)=\delta$ 。
证明：当 $\delta=n-1$ 时 $G=K_n$ ，所以 $k(G)=n-1=\delta_{\circ}$ 。当 $\delta=n-2$ 时，若顶点 $v_1, v_2$ 不相邻，则对任意第 3 个顶点 $v_3, G$ 中有边 $\left\{v_1, v_2\right\},\left\{v_2, v_3\right\}$ 。此时对任意 $n-3$ 个顶点构成的子集 $V^{\prime}$ ，均有 $G-V^{\prime}$ 连通（在 $G$ 中删去任意 $n-3$ 个顶点依然连通）。所以 $k(G) \geqslant n-2=\delta$ 。由定理 $11.1, ~ \lambda(G) \leqslant \delta$ ，即得 $k(G)=\delta$ 。

定义 $11.4(k$－连通的）若图 $G$ 的 $k(G) \geqslant k$ ，称 $G$ 为 $k$－连通的。
定义 $11.5(k$－边连通的）若图 $G$ 的 $\lambda(G) \geqslant k$ ，称 $G$ 为 $k$－边连通的。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：霍夫曼算法

下一篇：割点与块

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