最后更新: 2025-01-22 09:43 ● 参与者查看: 19 次纠错分享参与项目词条搜索

生成树与割集

前面我们讨论了树本身的性质，本节讨论树作为一个图的子图的情况。
生成树
定义 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$ 。

上一篇：树及其性质

下一篇：最小生成树

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