最后更新: 2025-01-22 09:43 查看: 147 次纠错评论(0) 课件开VIP

生成树与割集

前面我们讨论了树本身的性质，本节讨论树作为一个图的子图的情况。
生成树
定义 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$ 中，另一个端点在 $\overline{V_1}$ 中的所有边组成的集合称为 $G$ 的一个断集（或称边割），记为 $E\left(V_1 \times \bar{V}_1\right)$ ，简记为 $\left(V_1, \bar{V}_1\right)$ 。当 $\left|\left(V_1, \bar{V}_1\right)\right|=1$ 时，$\left(V_1, \bar{V}_1\right)$

中的那条边称为割边（或桥）。
显然，割集是断集，反之不一定。

对于连通图 $G(V, E)$ ，删去一个割集 $D$ ，得两个分支，设它们的顶点分别为 $V_1$ 和 $\bar{V}_1$ ，割集 $D$ 是 $G$ 中一个端点在 $V_1$ 中，另一个端点在 $\bar{V}_1$ 中的边的全体。如果在连通图 $G$ 中，删去一个断集而不是一个割集，那么将得到两个以上连通分支。

割集与回路
现在我们给出回路和割集的一些性质，这里不妨假设 $G$ 是连通图。
定理 10.4 任何一条回路和任何生成树的余树至少有一条公共边。
证明：如果一条回路和一棵生成树的余树没有公共边，则表示该回路在该生成树中。这与树的定义矛盾。

定理10．5 任何一个割集和任何一棵生成树至少有一条公共边。
证明：如果一个割集和一棵生成树没有公共边，则删去该割集后留下一棵完整的生成树，也就是说，删去一个割集后，不能将图 $G$ 分为两个分支，这与割集的定义相矛盾。

定理10．6 任何一条回路和任何一个割集有偶数条公共边。
证明：从连通图 $G$ 中删去一个割集 $D$ 后，得到彼此不连通的两个顶点子集 $V_1$ 和 $V_2$ ，考察其中任意一条回路 $C$ 。
（1）如果 $C$ 中所有顶点在 $V_1$（或 $V_2$ ）中，则 $C$ 与 $D$ 没有公共边。
（2）如果 $C$ 中顶点既有一些在 $V_1$ 中，又有一些在 $V_2$ 中，先看 $D$ 中任何一边，它的一个端点在 $V_1$ 中，另一个端点在 $V_2$ 中，且 $G$ 中除 $D$ 中边以外，不再有任何连接 $V_1$ 与 $V_2$ 中的顶点。现从 $V_1$中（也可以从 $V_2$ 中）的一个顶点出发，沿 $C$ 行走到 $V_2$ 中的某些顶点又回到 $V_1$ ，这样在 $V_1$ 与 $V_2$ 之间来回行走，最后回到 $V_1$ 的出发点。因此，回路 $C$ 中必有偶数条割集 $D$ 中的边。
在连通图 $G$ 中，给定生成树后，我们可以给出基本割集和基本回路的概念。
定义 10.6 设连通图 $G$ 中给定生成树 $T$ ，对于只包含 $T$ 中的一条枝的割集，称此割集为关于 $T$ 的基本割集。

在连通图 $G$ 中，对于给定的生成树 $T$ ，每一条枝恰对应唯一的一个基本割集。因为从生成树 $T$ 中删去一条枝，将 $T$ 分为两棵树，它将 $G$ 的顶点集 $V$ 划分为彼此不连通的两个顶点子集 $V_1$ 和 $\bar{V}_1$ ，在 $G$ 中这两个顶点集之间的连边，便是对应这一条枝的唯一的基本割集。

连通图 $G$ 有 $e$ 条边，$n$ 个顶点，给定的生成树 $T$ 应有 $n-1$ 条枝，所以恰有 $n-1$ 个基本割集，这些割集的全体称为生成树 $T$ 的基本割集组。

定义 10.7 设连通图 $G$ 中给定生成树 $T$ ，在 $T$ 中加一条弦，恰产生一条回路，称此回路为关于 $T$ 的基本回路。

由定理 10.1 的等价定义（4），可知在 $T$ 中加一条弦，产生唯一的回路。
连通图 $G$ 有 $e$ 条边，$n$ 个顶点，给定的生成树 $T$ 应有 $n-1$ 条枝，$e-n+1$ 条弦，所以恰有 $e-n+1$ 条基本回路，这些回路的全体称为生成树 $T$ 的基本回路组。

有关基本割集和基本回路之间的联系，请见习题 $1 0 . 1 3$ 和习题 10．14。

树的基本变换
设 $T$ 是连通图 $G$ 的一棵生成树， $\bar{e}$ 是任意一弦，则 $T \cup \bar{e}$ 恰产生一条基本回路 $C, e$ 是 $C$上 $T$ 的任意一枝，显然，$(T \cup \bar{e})-e$ 仍然是一棵生成树。

定义10．8（树的基本变换）设连通图 $G$ 的生成树 $T$ ，通过上述加一弦，再删去一枝得到另一棵生成树，这种变换称为树的基本变换。

定义 10.9 （距离）设连通图 $G$ 的生成树 $T_i$ 和 $T_j$ ，出现在 $T_i$ 而不出现在 $T_j$ 的边数称为 $T_i$ 和 $T_j$ 的距离，记为 $d\left(T_i, T_j\right)$ 。

容易看出 $d\left(T_i, T_j\right) \geqslant 0$ 。如果 $T_i=T_j$ ，则 $d\left(T_i, T_j\right)=0$ ；反之亦然。并且 $d\left(T_i, T_j\right)=d\left(T_j, T_i\right)$ 。
定理 10.7 设连通图 $G, T_1$ 和 $T_2$ 是 $G$ 的两个不同的生成树，则由 $T_1$ 通过有限次树的基本变换可以得到 $T_2$ 。

证明：因为 $T_1 \neq T_2, d\left(T_1, T_2\right)=d\left(T_2, T_1\right) \neq 0$ ，所以存在边 $e_1 \in T_2$ ，但 $e_1 \notin T_1$ ，于是 $T_1 \cup e_1$ 包含一条基本回路，显然这条回路上的边不全在 $T_2$ 中，那么存在边 $e_2 \in T_1$ ，但 $e_2 \notin T_2$ ，设 $T_1{ }^1=\left(T_1 \cup e_1\right)-e_2, T_1{ }^1$无回路并且边数为 $n-1$ ，因此 $T_1{ }^1$ 还是一棵树，并且 $d\left(T_1{ }^1, T_2\right)=d\left(T_1, T_2\right)-1$ 。如果 $d\left(T_1{ }^1, T_2\right) \neq 0$ ，重复上述步骤，经过有限步以后，必有某 $k$ 使得 $d\left(T_1{ }^k, T_2\right)=0$ ，即 $T_1{ }^k=T_2$ 。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：树及其性质

下一篇：最小生成树

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