最后更新: 2025-01-22 09:43 查看: 106 次反馈能力测评会员8.2元/月赞助

生成树与割集

前面我们讨论了树本身的性质，本节讨论树作为一个图的子图的情况。
生成树
定义 10.2 （生成树）图 $G$ 的生成子图是树 $T$ ，称 $T$ 为 $G$ 的生成树。从 $G$ 中删去 $T$ 的边，得到的图称为 $G$ 的余枝，记为 $\bar{T} 。 T$ 中的边称为树枝（或枝）。 $\bar{T}$ 中的边称为 $G$ 的弦（或连枝）。

由定义 10.2 ，只有连通图才有生成树；而且连通图的生成树不唯一，至少有一棵；生成树 $T$ 和余枝 $\bar{T}$ 成对出现。可以通过不断地删去图 $G$ 中的回路中的边得到一棵生成树。有如下定理。

定理 $10.3 G$ 是连通图当且仅当 $G$ 有生成树。
证明：$\Leftarrow$ 因为生成树是连通图，显然，$G$ 是连通图。

$\Rightarrow$ 采用构造方法来证明。设 $G$ 是连通图，若 $G$ 没有回路，则 $G$ 本身就是生成树。若 $G$只有一条回路，从这条回路中删去一条边，仍保持连通，得到一棵生成树；若 $G$ 中有多条回路，则重复上述过程，直到得到一棵生成树为止。

设连通图 $G$ 有 $n$ 个顶点，$e$ 条边，那么 $G$ 的任意一棵生成树有 $n-1$ 条枝，$e-n+1$ 条连枝。
设图 $G$ 有 $n$ 个顶点，$e$ 条边，$\omega$ 个分支，$n, e, \omega$ 之间有两个简单的关系式：因为每个分支至少有一个顶点，所以有 $n \geqslant \omega$ ，即 $n-\omega \geqslant 0$ ；然而由例 8.2 可知 $e \geqslant n-\omega$ ，即 $e-n+\omega \geqslant 0$ 。

定义 10.3 （秩，零度）设图 $G$ 有 $n$ 个顶点，$e$ 条边，$\omega$ 个分支，称 $n-\omega$ 为图 $G$ 的秩，称 $e-n+\omega$ 为图 $G$ 的零度。

显然 $G$ 的秩是 $G$ 的各分支中生成树的枝数之和，$G$ 的零度是 $G$ 的各分支中生成树的连枝数之和。对于连通图 $G$ 来说，它的秩为 $n-1$ ，零度为 $e-n+1$ 。

割集与断集
割集是图论中的一个重要概念，它与树和回路的概念有密切的联系。我们先引进割集的概念。

定义 10.4 （割集）设 $D$ 是图 $G$ 的一个边集，若在 $G$ 中删去 $D$ 的全部边后所得图的秩减少 1 ，而 $D$ 的任何真子集均无此性质，则称 $D$ 为 $G$ 的割集。

定义10．5（断集）设图 $G$ 顶点非空子集为 $V_l \subset V$ ，在 $G$ 中一个端点在 $V_1$ 中

免费注册看余下 70%

非VIP会员每天5篇文章，开通VIP 无限制查看

《高等数学》难点解析

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

高等数学测评 函数与极限一元函数微分学一元函数积分学微分方程空间向量与代数多元微分学多元积分学无穷级数

《线性代数》难点解析

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

线性代数测评 行列式矩阵向量空间

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

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

概率统计测评 事件与概率一维随机变量与事件多维随机变量与事件随机变量的数字特征大数定律与中心极限定理统计量与抽样分布参数估计假设检验

上一篇：树及其性质

下一篇：最小生成树

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