最后更新: 2025-01-21 17:02 查看: 27 次反馈刷题

无向图的点割集

## 无向图的点割集
定义7－2．4 无向连通图G＝＜V，E＞中，若存在 $V 1 \subset V$ 且 $V 1 \neq \varnothing$ ，使得 G 删除了 V 1所有点后所得的子图不连通，而若删除 V 1 的任何真子集后，所得的子图仍是连通图，则称 $V_1$ 是 $G$ 的一个点割集。若 $\left|V_1\right|=1$ ，则称为割点。
 ![图片](/uploads/2025-01/e9086c.jpg)
 
## 无向图的边割集
－定义7－2．5 无向连通图 $G=<V, E>$ 中，若存在 $E 1 \subset E$ 且
$E 1 \neq \varnothing$ ，使得 G 删除了 E 1 所有边后所得的子图是不连通图，而若删除了 E1的任何真子集后，所得的子图仍是连通图，则称E1是G的一个边割集。若 $|E 1|=1$ ，则称为割边或桥。
 ![图片](/uploads/2025-01/755bee.jpg)
 
 ## 点连通度
－设G为无向连通图，称

$$
k(G)=\min \left\{\left|V^{\prime}\right| \mid V^{\prime} \text { 为 } G \text { 的点割集 }\right\}
$$

为 $G$ 的点连通度。
－连通度是为了产生一个不连通图需要删去的点的最少数目。
－规定
－非连通图的点连通度为 0
－完全图 $K_n(n \geq 1)$ 的点连通度为 $n-1$
－存在割点的连通图的点连通度为 1 。

## 边连通度
－设G为无向连通图，称

$$
\lambda(G)=\min \left\{\left|E^{\prime}\right| \mid E^{\prime} \text { 为 } G \text { 的边割集 }\right\}
$$

为 $G$ 的边连通度。
－连通度是为了产生一个不连通图需要删去的边的最少数目。
－规定：
－非连通图的边连通度为 0
－完全图 $K_n(n \geq 1)$ 的边连通度为 $n-1$
－存在割边的连通图的边连通度为 1 。

例2-1 求图的点连通度和边连通度。

![图片](/uploads/2025-01/009ad4.jpg)
 
 
 定理7－2．2 无向图 G 满足 $k ( G ) \leq \lambda( G ) \leq \delta( G )$
例2－2（1）给出一些无向简单图，使得 $K=\lambda=\delta$ 。
（2）给出一些无向简单图，使得 $K<\lambda<\delta$ 。
（1）$n$ 阶无向完全图 $K_n$ 和 $n$ 阶零图 $N_n$ 都满足要求。
（2）
 ![图片](/uploads/2025-01/a83ad9.jpg)
 
 
 定理7-2.3 连通无向图G=<V,E>的结点v是割点的充分必要条件是存在两个结点u和w，使得结点u和w的每条路都通过v。

证明：若结点 $v$ 是连通图 $G=\langle V, E>$ 的一个割点，设删去 $v$ 得到子图G＇，则 $G^{\prime}$ 至少包含两个连通分支。设其为 $G _1=\left\langle V _1, E _1>, G _2=< V _2, E _2>\right.$ ，任取 $u \in V _1, w \in V _2$ ，因为 $G$ 是连通的，故在 $G$ 中必有一条连接 u 和 w 的路 C ，但 u 和 w 在 G ，中属于两个不同的连通分支，故 u 和 w 必不连通，因此C必须通过 v ，故 u 和 w 之间的任意一条路都通过 v 。

反之，若连接图 G 中某两个结点的每一条路都通过 v ，删去 v 得到子图 $G ^{\prime}$ ，在 $G ^{\prime}$ 中这两个结点必然不连通，故 v是图G的割点。

刷题

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

上一篇：连通图与连通分支

下一篇：有向图连通

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