离散数学（八）—

离散数学（八）——图和树

一、图基础

1.基础概念

这里我们直接略去无向图、有向图、顶点集、边集、关联、端点、混合图、(非)标定图、关联、邻接等的概念。但需要知道，通常将一幅图记为 $𝐺$ ，以 $𝑉 (𝐺), 𝐸 (𝐺)$ 表示它的顶点集和边集， $| 𝑉 (𝐺) |, | 𝐸 (𝐺) |$ 表示它的顶点数和边数。

假如 $| 𝑉 (𝐺) | = 𝑛$ ，也就是图有 $𝑛$ 个顶点，那么称之为 $𝑛$ 阶图。如果 $| 𝐸 (𝐺) | = 0$ ，也就是图中没有边，那么称之为零图。同样地，记 $𝑛$ 阶零图为 $𝑁_{𝑛}$ ，它是有 $𝑛$ 个顶点的零图，这其中 $𝑁_{1}$ 称为平凡图。

虽然图的定义要求顶点数不为 $0$ ，但是我们依然约定当顶点集为空集时，称图为空图。

对于一条边，它有两种特殊状态。一种是， $𝑒 = (𝑣, 𝑣)$ ，这是在说这条边关联同一个顶点，那么称之为环；另一种是， $𝑒 = (𝑢, 𝑣)$ 存在的同时，还有另一条边 $𝑒^{'} = (𝑢, 𝑣)$ ，也就是这两条边都关联同样的顶点，那么称它们为重边。

而对于不存在环和重边的图，称为简单图。

对于有向图中的一个顶点 $𝑣 \in 𝑉$ ，它的入度是指以 $𝑣$ 为终点的有向边的条数，记为 $𝑑^{-} (𝑣)$ ；同样地，也有出度，是指以 $𝑣$ 为起点的有向边的条数，记为 $𝑑^{+} (𝑣)$ 。入度和出度之和，称为顶点的度数，也就是 $𝑑 (𝑣) = 𝑑^{-} (𝑣) + 𝑑^{+} (𝑣)$ 。

在无向图中，如果一个顶点的度数为 $1$ ，那么称它为悬挂顶点，其关联的边称为悬挂边。而度数为 $0$ 的点称为孤立顶点。

2.握手定理

定理 1.（握手定理）

对于一条有向边，有始必有终，因此全图入度之和与出度之和相等；而无向图中的每条边关联两个顶点，因此所有顶点的度数之和等于边数的两倍：

(1)对无向图： $\sum 𝑑 (𝑣) = 2 | 𝐸 |$ ；
(2)对有向图： $\sum 𝑑^{-} (𝑣) = \sum 𝑑^{+} (𝑣) = | 𝐸 |$ 。

推论 1.（奇度顶点定理）

称度数为奇数的顶点为奇度顶点，度数为偶数的顶点为偶度顶点。由于总度数之和必为偶数，因此奇度顶点的个数必然是偶数。

遍历所有顶点的度数。我们将图 $𝐺$ 的最小度记为 $𝛿 (𝐺) = min {𝑑 (𝑣)}$ ，它是所有顶点度数中的最小值；将最大度记为 $Δ (𝐺) = max {𝑑 (𝑣)}$ ，它是所有顶点度数中的最大值。

那么，若 $𝐺$ 是简单图，那就必有 $Δ (𝐺) \leq 𝑛 - 1$ 。

3.正则图，完全图和二部图

假如一个图 $𝐺$ 的所有顶点的度数都等于 $𝑘$ ，那么称 $𝐺$ 为 $𝑘$ 正则图。注意这并不要求图 $𝐺$ 是简单图。

当 $𝐺$ 是简单图时，如果任意两个顶点之间都有边，那么称之为完全图。当图中具有 $𝑛$ 个顶点，称为 $𝑛$ 阶完全图，记为 $𝐾_{𝑛}$ 。

对于一个图 $𝐺$ ，现在我们将它的顶点集 $𝑉$ 划分为两部分 $𝑉_{1}, 𝑉_{2}$ 。如果存在一种划分，使得原本图中所有存在的边所关联的两个顶点，一个在 $𝑉_{1}$ 中而另一个在 $𝑉_{2}$ 中，或者说不存在原有的边连接了 $𝑉_{1}$ 中的两个顶点或 $𝑉_{2}$ 中的两个顶点，那么称 $𝑉_{1}, 𝑉_{2}$ 是 $𝑉$ 的一个二部划分，图 $𝐺$ 称为二部图。

假如二部图 $𝐺 = (𝑉, 𝐸)$ 的顶点集具有一个二部划分 $𝑉_{1}, 𝑉_{2}$ 。若 $𝑉_{1}$ 中的任一顶点，与 $𝑉_{2}$ 中的所有顶点都恰好有一条边关联，那么称 $𝐺$ 为完全二部图。

4.子图

给定图 $𝐺 = (𝑉, 𝐸), 𝐺^{'} = (𝑉^{'}, 𝐸^{'})$ 。假如 $𝑉^{'} \subseteq 𝑉, 𝐸^{'} \subseteq 𝐸$ ，那么称 $𝐺^{'}$ 是 $𝐺$ 的子图。其中，假如 $𝑉 = 𝑉^{'}$ ，那么就称 $𝐺^{'}$ 是 $𝐺$ 的生成子图。

二、图的连通

1.通路与回路

首先假设图 $𝐺 = (𝑉, 𝐸)$ ，那么它的一条通路 $𝛤 = 𝑣_{0} 𝑒_{1} 𝑣_{1} 𝑒_{2} \dots 𝑒_{𝑛} 𝑣_{𝑛}$ ，是从通路端点 $𝑣_{0}$ 到 $𝑣_{𝑛}$ 的经过边 $𝑒_{1}, 𝑒_{2}, \dots, 𝑒_{𝑛}$ 的一条路，其长度为 $𝑛$ 。假如 $𝑣_{0} = 𝑣_{𝑛}$ ，那么称此通路为回路。

若一条通路或回路不含有重复的边，则称为简单通路或简单回路。若一条通路中不含有重复的顶点，则称为初级通路，或称为路径。若一条回路中除端点外不含重复的顶点，则称为初级回路，或称为圈。

在有向图中，上述概念只需添加“有向”二字即可。

假设图 $𝐺 = (𝑉, 𝐸)$ 有 $𝑛$ 个顶点，那么给出以下定理：

(1)若存在从 $𝑢$ 到 $𝑣$ 的通路，那么必然存在从 $𝑢$ 到 $𝑣$ 的长度小于等于 $𝑛 - 1$ 的初级通路；
(2)若存在从 $𝑢$ 到自身的回路，那么必然存在从 $𝑢$ 到自身的长度小于等于 $𝑛$ 的初级回路。

2.无向图的连通

假设图 $𝐺 = (𝑉, 𝐸)$ 是无向图。如果顶点 $𝑢, 𝑣$ 间存在通路，就称 $𝑢$ 和 $𝑣$ 是可达的，并记为 $𝑢 \leftrightarrow 𝑣$ 。约定顶点与顶点本身总是可达的。

若在图中任意两个顶点都是可达的，那么称 $𝐺$ 是连通无向图。当图 $𝐺$ 是简单图、并且是连通图时总存在 $| 𝐸 | \geq | 𝑉 | - 1$ 。

如果无向图中存在“独立”的几部分，也就是这几部分之间不存在边将其连通，则称这几个部分(是 $𝐺$ 的子图)为 $𝐺$ 的连通分支。我们将 $𝐺$ 的连通分支数记为 $𝑝 (𝐺)$ 。

如果在图 $𝐺$ 中存在某条边 $𝑒$ ，将其删去之后 $𝑝 (𝐺)$ 发生变化¹¹ 应该说，必然是增大，也就是产生了将原来的连通分支分为两个连通分支，则称这条边 $𝑒$ 为 $𝐺$ 的割边，或称为桥。

3.有向图的连通

假设图 $𝐺 = (𝑉, 𝐸)$ 是有向图。如果从顶点 $𝑢$ 到 $𝑣$ 间存在通路，就称 $𝑢$ 可达 $𝑣$ ，并记为 $𝑢 \to 𝑣$ 。若在 $𝑢 \to 𝑣$ 的同时有 $𝑣 \to 𝑢$ ，那么就记 $𝑢 \leftrightarrow 𝑣$ 。也同样约定总有 $𝑢 \leftrightarrow 𝑢$ 。

如果 $𝐺$ 中任意两个顶点 $𝑢, 𝑣$ 中都存在 $𝑢 \leftrightarrow 𝑣$ ，那么称 $𝐺$ 为强连通有向图；而如果 $𝑢 \to 𝑣$ 和 $𝑣 \to 𝑢$ 中必有其一成立，那么称 $𝐺$ 为单向连通有向图；如果 $𝐺$ 的基图²² 有向图的基图，是指将所有有向边都视作无向边之后生成的无向图。是无向连通图，那么称 $𝐺$ 为弱连通有向图。

为了判定有向图 $𝐺$ 是强连通的，只需要在图中寻找一条经过每个顶点至少一次的有向回路。因此，强连通有向图是单向连通有向图；而单向连通有向图也是弱连通有向图。

4.领接矩阵

邻接矩阵在关系中已经介绍过，不再赘述。显然无向图的邻接矩阵必是对称矩阵，而有向图则不一定。有向图的领接矩阵中，行中元素的和是此行对应顶点的出度，而列中元素的和是此列对应顶点的入度。简单图的邻接矩阵中元素只有 $0, 1$ 两种。

对于图的邻接矩阵 $𝐴$ ，以普通的乘法来计算它的幂，那么 $𝐴^{𝑘}$ 就是表明两个顶点间长度为 $𝑘$ 的通路的条数；因此以关系中的特殊乘法来说，就只是判断是否存在长度为 $𝑘$ 的通路。

而记 $𝐵 = 𝐴 + 𝐴^{2} + \dots + 𝐴^{𝑛 - 1}$ ，这个矩阵表明两个顶点间长度小于等于 $𝑛 - 1$ 的通路的条数。这样，将这个矩阵中的元素单位化，形成一个只有 $0, 1$ 的矩阵 $𝑃$ ，这就是图 $𝐺$ 的可达矩阵，相当于关系中的传递闭包。因此可达矩阵同样可以使用 $Warshall$ 算法求出。

三、树基础

树是一种特殊的图。

1.无向树

设图 $𝐺 = (𝑉, 𝐸)$ 是简单无向图。若 $𝐺$ 是连通图，并且没有回路，那么称 $𝐺$ 是无向树，可以记为 $𝑇 = (𝑉, 𝐸)$ 。将无向树中度数为 $1$ 的顶点称为树叶，度数大于等于 $2$ 的称为分支点。如果图中存在多个无回路的连通分支，那么称 $𝐺$ 是森林。

说一个图是树时，默认此树为无向树。

设图 $𝐺 = (𝑉, 𝐸)$ 是简单无向图。那么以下四个命题互相等价：

命题 1.

(1)

𝐺

是树，也即

𝐺

是连通图且没有回路；
(2)

𝐺

的任意两个顶点之间存在唯一的通路；
(3)

𝐺

是连通的，并且任意一条边都是桥；
(4)

𝐺

虽然没有回路，但在任意两个不相邻的顶点间加一条边，会得到唯一一个、并且含有此新边的回路。

以下四个命题也互相等价：

命题 2.

(1)

𝐺

是树，也即

𝐺

是连通图且没有回路；
(2)

𝐺

是连通的，并且任意一条边都是桥；
(3)

𝐺

中没有回路，并且

| 𝐸 | = | 𝑉 | - 1

；
(4)

𝐺

是连通的，并且

| 𝐸 | = | 𝑉 | - 1

。

树中的等式 $| 𝐸 | = | 𝑉 | - 1$ 与握手定理结合，常常是证明的要点。

2.根树

如果一个有向图的基图是树，那么称这个图为有向树。而如果一个有向树 $𝑇$ 有且仅有一个顶点 $𝑟$ 的入度为 $0$ ，那么称 $𝑇$ 是以 $𝑟$ 为根的根树。根树中的顶点也称为节点。出度为 $0$ 的节点称为叶子，出度不为 $0$ 的称为内部顶点。

我们再次略去父亲。儿子、祖先、后代、子树的定义。而所谓的节点 $𝑢$ 的层数，是指从 $𝑟$ 到 $𝑢$ 的唯一通路的长度。因此，根的层数是 $0$ 。而树 $𝑇$ 的高度，是指从 $𝑟$ 到 $𝑇$ 的叶子的最长通路的长度。

如果根树的每个节点的出度都小于等于 $𝑚$ ，那么称此树为 $𝑚$ 元树。当每个节点的出度不是 $𝑚$ 就是 $0$ 时，则称此树为满 $𝑚$ 元树，或称正则 $𝑚$ 元树。而对于满 $𝑚$ 元树来说，如果每个叶子的层数都等于树高，则称之为完全 $𝑚$ 元树。若高度为 $ℎ$ 的 $𝑚$ 元树的叶子的层数要么是 $ℎ$ 要么是 $ℎ - 1$ ，则称之为平衡 $𝑚$ 元树。

四、平面图

一个平面图，是指一个能画在平面上、而任两条边之间不存在除顶点外的其他交点的图。现在假设图 $𝐺$ 是平面图。

平面图中的一个面 $𝑅 = (𝑉, 𝐸)$ ，是由它的若干条边包围而成、且不含图的顶点和边的区域。而包围面 $𝑅$ 的若干条边构成的回路，称为此面的边界，这条回路的长度称为此面的度，并记为 $deg (𝑅)$ 。由平面图的“外部”的边包围的无穷大的面称为平面图的外部面，而其他的面都称为内部面。

1.几个定理

与握手定理同样的原理，一条边必是两个面的边界，因此平面图的所有面的度数之和等于边数的两倍： $\sum deg (𝑅) = 2 | 𝐸 |$

第二个重要的公式是欧拉公式。记连通平面图有 $𝑛$ 个顶点、 $𝑚$ 条边、 $𝑑$ 个面，那么恒有 $𝑛 - 𝑚 + 𝑑 = 2$ 。

记 $𝑔 (𝐺)$ 是图 $𝐺$ 中长度最小的回路的长度，称为 $𝐺$ 的围长。在平面图中，围长显然就是所有面中最小的度数。记 $𝑙 = 𝑔 (𝐺)$ ，那么由第一条定理，应有 $𝑙 \times 𝑑 \leq 2 𝑚$ ；而由欧拉公式，应有 $𝑑 = 2 + 𝑚 - 𝑛$ 。联合两式，得到：

𝑚 \leq \frac{𝑙}{𝑙 - 2} (𝑛 - 2)

2.极大平面图

设简单平面图 $𝐺 = (𝑉, 𝐸)$ 有至少四个顶点。若在 $𝐺$ 中任意两个不相邻顶点间添加一条新边、都将使平面图变成非平面图，那么称 $𝐺$ 为极大平面图。

极大平面图具有以下性质：

(1)极大平面图是连通图；
(2)极大平面图中没有桥；
(3)极大平面图的每个面的度数都为 $3$ ；
(4)记 $𝑑$ 为面数、 $𝑚$ 为边数，那么极大平面图中 $3 𝑑 = 2 𝑚$ ；
(5)极大平面图中 $𝛿 (𝐺) \geq 3$ ；
(6)设 $𝑣$ 是极大平面图中的任一顶点。那么 $𝑣$ 必与其相邻顶点构成回路。

利用 $3 𝑑 = 2 𝑚$ 与欧拉定理，可以得到另外两条等式：

𝑚 = 3 𝑛 - 6, 𝑑 = 2 𝑛 - 4

既然对于极大平面图来说上面两条等式成立，那么更具有一般意义的简单平面图必有下列两条不等式：

𝑚 \leq 3 𝑛 - 6, 𝑑 \leq 2 𝑛 - 4

五、欧拉图

设无向连通图 $𝐺 = (𝑉, 𝐸)$ 。 $𝐺$ 中的一条能够经过所有边的简单通路或简单回路称为 $𝐺$ 的欧拉通路或欧拉回路。而含有欧拉通路的图称为半欧拉图，含有欧拉回路的图称为欧拉图。

一个无向连通图 $𝐺 = (𝑉, 𝐸)$ 中存在欧拉回路的充要条件是： $𝐺$ 中所有顶点的度数都为偶数。

而若 $𝐺$ 中只有两个度数为奇数的顶点，那么图中存在欧拉通路。

六、哈密顿图

类似于欧拉图中的定义。但它是以初级通路为基础。

设无向图 $𝐺$ 。 $𝐺$ 中的一条能够经过所有边的初级通路或初级回路称为 $𝐺$ 的哈密顿通路或哈密顿回路。而含有哈密顿通路的图称为半哈密顿图，含有哈密顿回路的图称为哈密顿图。

对于无向图中的一条通路 $𝛤 = 𝑣_{0} 𝑒_{1} 𝑣_{1} 𝑒_{2} \dots 𝑒_{𝑛} 𝑣_{𝑛}$ ，如果不存在其他顶点 $𝑣 \in 𝑉, 𝑣 \neq 𝑣_{𝑖}$ 使 $𝑣$ 与 $𝑣_{0}$ 或 $𝑣_{𝑛}$ 相邻，那么称此通路为极长通路。如果此极长通路又是初级通路，那么称之为极长初级通路。

一个简单图存在哈密顿通路的充分条件是：如果 $𝑛$ 阶简单图 $𝐺$ 中的任意两个顶点的度数之和都大于等于 $𝑛 - 1$ ，那么 $𝐺$ 存在哈密顿通路。这里要求 $𝑛 \geq 2$ 。

因此，若 $𝑛 (𝑛 \geq 3)$ 阶的简单图 $𝐺$ 中的任意两个顶点的度数之和都大于等于 $𝑛$ ，那么 $𝐺$ 存在哈密顿回路；或者，任意顶点的度数都大于等于 $\frac{𝑛}{2}$ ，那么 $𝐺$ 存在哈密顿回路。