最后更新: 2025-01-21 17:02 查看: 94 次纠错评论(0) 课件开VIP

无向图的点割集

## 无向图的点割集
定义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的割点。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

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

下一篇：有向图连通

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