最后更新: 2025-01-22 10:06 查看: 62 次反馈刷题

连通度与块

点连通度与边连通度
为了衡量一个图的连通程度，我们要定义图的点连通度与边连通度。
定义 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$－边连通的。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：霍夫曼算法

下一篇：割点与块

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