第二章 树

2.1 树的概念与性质

★树的概念

森林

不含圈的图称为无圈图 (acyclic graph), 无圈图也称作森林 (forest).

树

树 (tree) 是连通的无圈图.

树的 $1$ 度点称为树叶(leaf).

注:

• (1)树与森林都是简单图;
• (2) 树与森林都是二部图.

树的应用

树是图论中应用最为广泛的一类图. 在理论上, 由于树的简单结构, 常常是图论理论研究的“试验田”. 在实际问题中, 许多实际问题的图论模型就是树.

族谱图与树

要把一个家族的繁衍情况简洁直观表达出来, 用点表示家族中成员, 成员x是成员y的儿女, 把点x画在点y的下方, 并连线. 如此得到的图, 是一棵树, 称为根树. 示意如下:

实际上, 根树是许多问题的模型, 如社会结构, 计算机数据结构, 数学中的公式结构, 分类枚举表示等.

化学中的分子结构与树

Arthur Cayley 1875年用树的模型研究了化学同分异构体的计数问题

如: C4H10的两种同分异构结构图模型为:

电网络中独立回路与图的生成树

早在19世纪, 图论还没有引起人们关注的时候, 物理学家Kirchhoff 就已经注意到电路中的独立回路与该电路中生成树的关系, 进而发现了Kirchhoff电流定律. 即: 如果电路是(n,m)图, 则独立回路的个数为m−n+1. 并且, 生成树添上生成树外的G的一条边, 就可以得到一独立回路.

总之, 树在图论研究和应用上都是十分典型的特殊图.

树的性质

定理1

每棵非平凡树至少有两片树叶.

证明: 设 $P=v_1{v}_2\dots v_k$ 是非平凡树 $T$ 中一条最长路, 则 $v_1$ 与 $v_k$ 在 $T$ 中的邻接点只能有一个, 否则, 要么推出 $P$ 不是最长路, 要么推出 $T$ 中存在圈, 这都是矛盾！即说明 $v_1$ 与 $v_k$ 是树叶.

定理2

图 $G$ 是树当且仅当 $G$ 中任意两点都被唯一的路连接.

证明:

“必要性”
若不然, 设 $P_1$ 与 $P_2$ 是连接 $u$ 与 $v$ 的两条不同的路. 则由这两条路的全部或部分将构成一个圈, 这与 $G$ 是树相矛盾.

“充分性”
首先, 因 $G$ 的任意两点均由唯一路相连, 所以 $G$ 是连通的.
其次, 若 $G$ 中存在圈, 则在圈中任取点 $u$ 与 $v$, 可得到连接 $u$ 与 $v$ 的两条不同的路, 与条件矛盾, 所以 $G$ 是无圈图.
综上, $G$ 是树.

★定理3

设 $T$ 是 $(n,m)$ 树, 则: $m=n-1$.

证明: 对 $n$ 作数学归纳.

当 $n=1$ 时, 等式显然成立; 设 $n=k$ 时等式成立. 考虑 $n=k+1$ 的树 $T$.

由定理1, $T$ 中至少有两片树叶, 设 $u$ 是 $T$ 中树叶, 考虑 $T_1=T-u$ , 则 $T_1$ 为 $k$ 阶树, 于是 $m(T_1)=k-1$, 得 $m(T)=k$.

这就证明了定理.

例

设 $T$ 为 $12$ 条边的树, 其顶点度为 $1,2,5$. 如果 $T$ 恰有 $3$ 个度为 $2$ 的顶点, 那么 $T$ 有多少片树叶？

解: 设 $T$ 有 $x$ 片树叶. 由 $m=n-1$ 得 $n=13$.
于是由握手定理得: $1\times x+2\times 3+5\times (10-x)=2\times 12$.
得 $x=8$.

推论

具有 $k$ 个分支的森林有 $n-k$ 条边.

证明: 设森林 $G$ 的 $k$ 个分支为 $T_i(1\le i\le k)$. 对每个分支, 使用定理3得:

$$m(T_i)=n_i-1,(n_i=|V(T_i)|)$$

所以:

$$m(G)=\sum _{i=1}^{k}m(T_i)=n-k$$

定理4

每个 $n$ 阶连通图的边数至少为 $n-1$.

证明: 如果 $n$ 阶空图 $G$ 不连通且有 $n$ 个分支. 给 $G$ 加入一条边最多减少 $G$ 的一个分支. 那么要使 $G$ 连通, 即一个分支, 则至少要加入 $n-1$ 条边.

注: 树也被称为最小连通图.

定理5

任意树 $T$ 的两个不邻接顶点之间添加一条边后, 可以得到唯一圈.

证明: 设 $u$ 与 $v$ 是树 $T$ 的任意两个不邻接顶点, 由定理2知: 有唯一路 $P$ 连接 $u$ 与 $v$. 于是 $P\cup \{uv\}$ 是一个圈.

显然,由 $P$ 的唯一性也就决定了 $P\cup \{uv\}$ 的唯一性.

例

设 $G$ 是树且 $\Delta \ge k$, 则 $G$ 至少有 $k$ 片树叶.

证明: 若不然, 设 $G$ 有 $n$ 个顶点, 至多 $k-1$ 个一度顶点, 由于 $\Delta \ge k$, 于是, 由握手定理得:

$$2m(G)=\sum _{v\in V(G)}d(v)\ge k-1+k+2(n-k)=2n-1>2n-2$$

所以, 有: $m(G)>n-1$, 与 $G$ 是树矛盾！

例

设 $G$ 是森林且恰有 $2k$ 个奇度点, 则在 $G$ 中有 $k$ 条边不重合的路 $P_1,P_2,\dots ,P_k$, 使得:

$$E(G)=E(P_1)\cup E(P_2)\cup \cdots \cup E(P_k)$$

证明: 对 $k$ 作数学归纳.

当 $k=1$ 时, $G$ 只有两个奇数度顶点, 此时, 容易证明, $G$ 是一条路;

设当 $k=t$ 时, 结论成立. 令 $k=t+1$.

在 $G$ 中一个分支中取两个一度顶点 $u$ 与 $v$, 令 $P$ 是连接 $u$ 与 $v$ 的唯一路, 则 $G-E(P)$ 是有 $2t$ 个奇数顶点的森林, 由归纳假设, 它可以分解为 $t$ 条边不重合的路之并, 所以 $G$ 可以分解为 $t+1$ 条边不重合的路之并.

注: 对图作某种形式的分解, 是图论的一个研究对象, 它在图结构分析中具有重要作用.

树的度序列问题

在第一章中, 介绍了判定一个非增非负序列是否为简单图的度序列定理. 下面介绍一个判定非增非负序列是否为树的度序列的简单方法.

定理

设 $S=\{d_1,d_2,\dots ,d_n\}$ 是 $n$ 个正整数的序列, 它们满足: $d_1\ge d_2\ge \dots \ge d_n,\sum d_i=2(n-1)$. 则存在一棵树 $T$, 其度序列为 $S$.

证明: 对 $n$ 作数学归纳.

当 $n=1$ 和 $2$ 时, 结论显然. 假设对 $n=k$ 时结论成立. 考虑 $n=k+1$.

首先, 序列中包含 $1$. 否则, 序列中数都大于等于 $2$, 序列之和大于 $2k$, 与条件 $\sum d_i=2(n-1)=2k$ 矛盾！

所以, $d_{k+1}=1$. 从序列中删掉 $d_1$ 和 $d_{k+1}$, 增加数 $d^{\ast }=d_1-1$ 放在它应该在的位置 (按从大到小排列). 得到序列 $S_1$. 该序列含 $k$ 个数, 序列和为 $2(k-1)$, 由归纳假设, 存在树 $T_1$, 它的度序列为 $S_1$.

现在, 增加结点 $v$, 把它和 $T_1$ 中点 $d^{\ast }$ 相连得到树 $T$. 树 $T$ 为所求.

2.2 ★树的中心与形心

离心率 $e(v)$

顶点 $v$ 的离心率 (eccentricity): $e(v)=\max \{d(u,v)|u\in V(G)\}$

半径 $r(G)$

图的半径 (radius): $r(G)=\min \{e(v)|v\in V(G)\}$

即所有点中最小离心率.

直径

图的直径 (diameter): (所有顶点中) 最大离心率.

注:

• (i) 通信网络中, 一般直径越小, 网络延迟越小;
• (ii) 亦可使用平均距离衡量; 事实上等价于衡量 $D(G)={\sum }_{u,v\in V(G)}d(u,v)$;
• (iii) 事实上, $D(G)$ 被称作 Wiener index. Harry Wiener 1947 年用其研究石蜡的沸点 (boiling point): Wiener 指标越大, 沸点越高.

中心点

图的中心点 (center): 离心率等于半径的点.

中心

图的中心: 中心点的集合.

Jordan 定理

(Jordan,1869) 每棵树的中心由一个点或两个相邻点组成.

证明: 对树 $T$ 的阶数 $n$ 作归纳. 当 $n=1$ 或 $2$ 时,结论显然成立.

设对 $n<k(k\ge 3)$ 的树结论成立. 设 $T$ 是 $k$ 阶树.

容易知道: 删掉 $T$ 的所有叶子, 得到的树 $T_1$ 的每个点的离心率比它们在 $T$ 中离心率减少 $1$ ($T$ 中叶子点的离心率比其邻点大 $1$ ).

又因 $T$ 的叶不能是中心点, 所以 $T$ 的中心点在 $T_1$ 中.

这样, 若点 $u$ 的离心率在 $T$ 中最小, 则在 $T_1$ 中依然最小 ($T_1$ 中每个点的离心率都比T中的对应点小 $1$), 即说明 $T$ 的中心点是 $T_1$ 的中心点(中心不变), 反之亦然.

因为 $T_1$ 的阶数 $<k$, 所以, 由归纳假设, $T_1$ 的中心为一个点或两个相邻点组成, 即证明 $T$ 的中心由一个点或两个相邻点组成.

注:
(1) Jordan定理事实上可以求树的半径 (只有一个中心点时剪叶的次数; 两个中心点时剪叶的次数+1) 以及直径 (只有一个中心点时半径的2倍; 两个中心点时半径的2倍−1).
(2) 确定图的中心有应用价值. 例如, 确定社区医院的修建位置, 就可以建模成求图的中心问题.

2.3 生成树

生成树的概念与性质

★生成树, 生成森林

图 $G$ 的一个生成子图 $T$ 如果是树, 称它为 $G$ 的一棵生成树 (spanning tree); 若 $T$ 为森林, 称它为 $G$ 的一个生成森林 (spanning forest).

用 $\tau (G)$ 表示 $G$ 的生成树棵数.

生成树的应用: 生成树协议

Radia Joy Perlman (born in 1951, 美国程序员和网络设计工程师) 于1981年设计了生成树协议 (Spanning Tree Protocol). 该协议是工作在OSI网络模型中的第二层(数据链路层)的通信协议.

生成树协议的主要目的是防止交换机冗余链路产生的环路. 用于确保以太网中无环路的逻辑拓扑结构. 从而避免了广播风暴, 大量占用交换机的资源.

定理

每个连通图至少包含一棵生成树.

证明: 如果连通图 $G$ 是树, 则其本身是一棵生成树; 若连通图 $G$ 中有圈 $C$, 则去掉 $C$ 中一条边后得到的图仍然是连通的, 这样不断去掉 $G$ 中圈, 最后得到一个 $G$ 的无圈连通子图 $T$, 它为 $G$ 的一棵生成树.

注:

• 定理的证明实际上给出了连通图 $G$ 的生成树的求法, 该方法称为 (删边) 破圈法. 利用破圈法, 显然也可以求出任意图的一个生成森林.
• 连通图 $G$ 的生成树一般不唯一！

推论

若 $G$ 是 $(n,m)$ 连通图, 则 $m\ge n-1$.

★生成树的计数: 凯莱递推计数法

收缩 $G\cdot e$

图 $G$ 的边 $e$ 称为被收缩 (contraction), 是指删掉 $e$ 后, 把 $e$ 的两个端点等同 (identify), 如此得到的图记为 $G\cdot e$.

定理 (Cayley, 1889)

设 $e$ 是 $G$ 的一条边 (非自环), 则有:

$$\tau (G)=\tau (G-e)+\tau (G\cdot e)$$

证明: 考虑 $G$ 的任一条边 $e$. $G$ 的生成树中包含边 $e$ 的棵数为 $\tau (G\cdot e)$, 而不包含 $e$ 的棵数为 $\tau (G-e)$. 即证.

例

利用凯莱递推法求下图生成树的棵数.

共 $8$ 棵生成树.

凯莱公式的缺点

1. 计算量很大;
2. 不能具体指出每棵生成树.

★生成树的计数: 矩阵树定理

矩阵树定理

设 $G$ 是顶点集合为 $V(G)=\{v_1,v_2,\dots ,v_n\}$ 的无环图 (loopless graph), 设 $L=(l_{ij})$ 是 $G$ 的 Laplacian 矩阵, 其中:

$$l_{ij}=\{\begin{array}{c}d(v_i),i=j\\ -a_{ij},i\ne j\end{array}$$

$a_{ij}$ 为邻接矩阵的元素, 则 $G$ 的生成树棵数为 $L$ 的任意一个元素 $l_{ij}$ 的代数余子式的值.

矩阵树定理的证明思路

① $L=M{M}^T$, 其中 $M$ 是 $G$ 的任一定向有向图的关联矩阵;

② $M$ 的任一 $n-1$ 阶子方阵的行列式是 $\pm 1$, 如果这 $n-1$ 条边对应一棵生成树;

③ $L$ 的任一代数余子式 $=M^{\ast }(M^{\ast }{)}^T$ 的, $M^{\ast }$ 是删除 $M$ 的任一行 $t$ 之后的矩阵.

例

利用矩阵树定理求下图生成树的棵数.

解: 图的 Laplacian 矩阵为:

$$L=\left(\begin{array}{cccc}2& -1& -1& 0\\ -1& 2& -1& 0\\ -1& -1& 3& -1\\ 0& 0& -1& 1\end{array}\right)$$

第一行第一列元素对应的代数余子式为:

$$(-1{)}^{1+1}\left|\begin{array}{ccc}2& -1& 0\\ -1& 3& -1\\ 0& -1& 1\end{array}\right|=3$$

例

(W. Borchardt, 1860; Cayley Formula) 证明 $\tau (K_n)=n^{n-2}$.

证法一: $K_n$ 的Laplacian矩阵为:

$$L(K_n)={\left(\begin{array}{cccc}n-1& -1& \cdots & -1\\ -1& n-1& \cdots & -1\\ & \cdots & & \\ -1& -1& \cdots & n-1\end{array}\right)}_{n\times n}$$

第一行第一列元素的代数余子式为:

$$(-1{)}^{1+1}{\left|\begin{array}{cccc}n-1& -1& \cdots & -1\\ -1& n-1& \cdots & -1\\ & \cdots & & \\ -1& -1& \cdots & n\end{array}\right|}_{(n-1)\times (n-1)}$$

所以: $\tau (K_n)=n^{n-2}$.

证法二: Prüfer code (1918)

$n-2$ 长的 $n$ 元 Prüfer 序列有 $n^{n-2}$ 个, 故 $\tau (K_n)=n^{n-2}$.

注: 例的证明有多种不同方法. 用矩阵树定理证明是最直接和便于计算的方法. 1967年, 加拿大数学家Moon用10多种方法证明了例, 之后又涌现出一些不同的证明方法.

Prüfer 序列

一棵标号树与一个 Prüfer 序列是唯一地对应的. 亦即在标号树和 Prüfer 序列之间构成一个双射. 构造双射是组合数学中的一种重要方法.

一棵标号树可以得到一个 Prüfer 序列:

• 第 $i$ 步, 取当前树中标号最小的顶点, 删去它并记其邻点的标号为序列中第 $i$ 个元素.
• 重复进行上述操作, 直到剩下的树恰有 $2$ 个顶点.
• 此时 Prüfer 序列包含恰好 $n-2$ 个元素.

一个 Prüfer 序列可以得到一棵标号树:

• 考虑集合 $A=\{1,2,\dots ,n\}$.
• 将序列中未出现在 $A$ 中的最小元素对应的点与序列中的第一个点连边.
• 然后从序列和 $A$ 中分别删除该元素, 重复上述操作 $n-2$ 次.
• 最后将集合中剩余的两个元素连边.

例

证明: 若 $e$ 为 $K_n$ 的一条边, 则: $\tau (K_n-e)=(n-2)n^{n-3}$.

证法一: 若 $e$ 为 $K_n$ 的一条边, 由 $K_n$ 中的边的对称性以及每棵生成树的边数为 $n-1$, $K_n$ 的所有生成树的总边数为: $(n-1)n^{n-2}$.

所以, 每条边 ($e$ 这条边) 出现在生成树的次数为:

$$\frac{(n-1)n^{n-2}}{\frac{1}{2}n(n-1)}=2n^{n-3}$$

所以, $K_{n-e}$ 对应的生成树的棵数为 (把包含 $e$ 的生成树减掉):

$$\tau (K_n-e)=n^{n-2}-2n^{n-3}=(n-2)n^{n-3}$$

证法二: 假设在 $K_n$ 中去掉的边 $e=v_1{v}_n$, 则 $K_n-e$ 的 Laplacian 矩阵为:

$$L=\left(\begin{array}{cccc}n-2& -1& \cdots & 0\\ -1& n-1& \cdots & -1\\ & \cdots & & \\ 0& -1& \cdots & n-2\end{array}\right)$$

于是由矩阵树定理:

$$\begin{array}{rl}\tau (K_n-e)=& \left|\begin{array}{ccccc}n-1& -1& \cdots & -1& -1\\ -1& n-1& \cdots & -1& -1\\ & & \cdots & & \\ -1& -1& \cdots & n-1& -1\\ -1& -1& \cdots & -1& n-2\end{array}\right|\\ =& \left|\begin{array}{ccccc}n-1& -1& \cdots & -1& -1\\ -1& n-1& \cdots & -1& -1\\ & & \cdots & & \\ -1& -1& \cdots & n-1& -1\\ -1& -1& \cdots & -1& n-1)\end{array}\right|+\left|\begin{array}{ccccc}n-1& -1& \cdots & -1& 0\\ -1& n-1& \cdots & -1& 0\\ & & \cdots & & \\ -1& -1& \cdots & n-1& 0\\ -1& -1& \cdots & -1& -1\end{array}\right|\\ =& n^{n-2}-2n^{n-3}\\ =& (n-2)n^{n-3}\end{array}$$

生成树计数的应用

例: 等效电阻

计算下图电网络中 1, 2 两点的等效电阻大小(数字代表电阻).

解: 用等效电阻直接计算如下:

那么 1,2 之间的等效电阻大小为 $\frac{5}{8}$.

换一个思路:

先计算生成树的棵数 (当然也可以枚举)

再计算分离 1,2 两点的生成 $2$-森林 ($2$ 个分支的森林) 的个数

可以发现分离 1,2 两点的生成森林的个数与生成树的棵数正好是 $\frac{5}{8}$.

这是巧合吗?

定理 (G. Sharpe, B. Spain, 1960)

令 $G$ 是一个无向连通图, $u,v$ 是 $G$ 的任意两个顶点. 则 $u,v$ 两点之间的等效电阻 $r_G(u,v)$:

$$r_G(u,v)=\frac{{\zeta }_G(u,v)}{\tau (G)}$$

其中 ${\zeta }_G(u,v)$ 表示分离 $u,v$ 两点的生成 $2$-森林的个数.

定理’ (G. Sharpe, B. Spain, 1960) 令 $G$ 是一个阶数至少为 $3$ 的无向连通图, $u,v$ 是 $G$ 的任意两个顶点. 则 $u,v$ 两点之间的等效电阻 $r_G(u,v)$:

$$r_G(u,v)=\frac{\det L(u,v)}{\det L(u)}$$

其中 $\det L(u,v)$ 为 Laplacian 矩阵中删除 $u,v$ 所对应行, 列后的行列式.

回路系统简介

弦, 树枝

设 $T$ 是连通图 $G$ 的一棵生成树, 把属于 $G$ 但不属于 $T$ 的边称为 $G$ 关于 $T$ 的弦 (chord), $T$ 中的边称为 $G$ 关于 $T$ 的树枝.

在上图中, 红色边导出图的一棵生成树. 则红色边为 $G$ 对应于该生成树的树枝, 紫色边为 $G$ 对应于该生成树的弦.

基本圈

设 $T$ 是连通图 $G$ 的一棵生成树, 由 $G$ 的对应于 $T$ 一条弦与 $T$ 中树枝构成的唯一圈 $C$, 称为 $G$ 关于 $T$ 的一个基本圈 (fundamental cycle).

若 $G$ 是 $(n,m)$ 连通图, 把 $G$ 对应于 $T$ 的 $m-n+1$ 个基本圈称为 $G$ 对应于 $T$ 的基本圈系统 (fundamental cycle system). 记为 $C_f$.

例如图 $G$ 和对应生成树 $T$：

基本圈为:

定理

设 $T$ 是连通图 $G=(n,m)$ 的一棵生成树, $C_1,C_2,\dots ,C_{m-n+1}$ 是 $G$ 对应于 $T$ 的基本圈系统. 定义: $1\cdot G_i=G_i,0\cdot G_i=\varnothing$, $G_i$ 是 $G$ 的回路 (这里指每个点都是偶度的子图). 则 $G$ 的回路组作成的集合对于该乘法和图的对称差运算构成数域 $F=\{0,1\}$ 上的 $m-n+1$ 维向量空间.

证明:

(1) 非空、两闭、8条容易证明.

(2) 首先证明 $C_1,C_2,\dots ,C_{m-n+1}$ 线性无关.
若不然, 设 $C_1,C_2,\dots ,C_{m-n+1}$ 线性相关, 那么存在一组不全为零的数 $a_1,a_2,\dots ,a_{m-n+1}$, 使得:

$$a_1{C}_1△a_2{C}_2△\cdots △a_{m-n+1}{C}_{m-n+1}=\varnothing$$

但是, 任意两个基本圈包含两条不同弦, 所以, 若某个 $a_k\ne 0$, 则

$$a_1{C}_1△a_2{C}_2△\cdots △a_{m-n+1}{C}_{m-n+1}\ne \varnothing$$

矛盾！故 $C_1,C_2,\dots ,C_{m-n+1}$ 线性无关.

其次证明 $G$ 的任意一个回路均可由 $C_1,C_2,\dots ,C_{m-n+1}$ 线性表出.
设 $B$ 是 $G$ 的任一回路, 显然, 它至少含一条弦, 不失一般性, 令:

$$B=\{e_{i_1},e_{i_2},\cdots e_{i_j},e_{i_{j+1}},\cdots ,e_{i_k}\}$$

其中: $e_{i_1},e_{i_2},\cdots e_{i_j}$ 为弦, $e_{i_{j+1}},\cdots ,e_{i_k}$ 为树枝.

又设包含弦 $e_{i_1},e_{i_2},\cdots e_{i_j}$ 的基本圈为 $C_{i_1},C_{i_2},\cdots C_{i_j}$.

令: $B_1=C_{i_1}△C_{i_2}△\cdots △C_{i_j}$.

显然, $B$ 中弦均包含在 $B_1$ 中, 于是 $B△B_1$ 只含树枝不含弦. 但是, 可以证明: 两个回路的对称差一定是回路. 因此 $B△B_1$ 中只含树枝不含弦是不可能的.

所以: $B△B_1=\varnothing$, 得 $B=B_1$. 故 $G$ 的任意一个回路均可由 $C_1,C_2,\dots ,C_{m-n+1}$ 线性表出.

定理说明, 连通图 $G$ 的所有回路作成子图空间的一个子空间, 该空间称为回路空间或回路系统.

例

求下图 $G$ 的回路空间的一个基底和它的全部元素.

解: 取 $G$ 的一棵生成树 $T$ 为:

$G$ 对于生成树 $T$ 的基本圈为:

$$\begin{array}{rl}{C}_1& =\{a,b,c\}\\ C_2& =\{a,b,d,e\}\\ C_3& =\{a,b,d,g,h\}\\ C_4& =\{d,f,g\}\end{array}$$

图形为:

所有可能的和为:

$$\begin{array}{lll}{B}_1& =C_1△C_2& =\{c,d,e\}\\ B_2& =C_1△C_3& =\{c,d,g,h\}\\ B_3& =C_1△C_4& =\{a,b,c,d,f,g\}\\ B_4& =C_2△C_3& =\{e,g,h\}\\ B_5& =C_2△C_4& =\{a,b,e,f,g\}\\ B_6& =C_3△C_4& =\{a,b,f,h\}\\ B_7& =C_1△C_2△C_3& =\{a,b,c,e,g,h\}\\ B_8& =C_1△C_2△C_4& =\{c,e,f,g\}\\ B_9& =C_1△C_3△C_4& =\{c,f,h\}\\ B_{10}& =C_2△C_3△C_4& =\{d,e,f,h\}\\ B_{11}& =C_1△C_2△C_3△C_4& =\{a,b,c,d,e,f,h\}\end{array}$$

例: 回路系统的一个应用

Kirchhoff 定律:

• (1) 任一点的电流和为零;
• (2) 任一个圈上的电压和是相应电流与电阻乘积的和.

对上面左图的三个圈 VYXV, VWYV 和 VWYXV 分别应用 Kirchhoff 第二定律得到方程:

• (1) $i_1{R}_1+i_2{R}_2=E$;
• (2) $i_3{R}_3+i_4{R}_4-i_2{R}_2=0$;
• (3) $i_1{R}_1+i_3{R}_3+i_4{R}_4=E$.

但第 (3) 式的信息是冗余的: (1)+(2) 可得到 (3). 这是因为 (3) 所对应的圈不是基本圈, 该圈可由 VYXV 和 VWYV 表出.

所以由基本圈系统的知识, 只要对 $n-m+1$ 个基本圈应用 Kirchhoff 第二定律列出相应公式, 再由 Kirchhoff 第一定律列出 $n-m+1$ 个电流公式即可联立解出电路的电阻, 电流和电压.

由电路的一个基本圈系统, 列出下面公式:

$$\begin{array}{lllc}& VYXV,& i_1{R}_1+i_2{R}_2& =E,\\ & VYZV,& i_2{R}_2+i_5{R}_5+i_6{R}_6& =0,\\ & VWZV,& i_3{R}_3+i_5{R}_5+i_7{R}_7& =0,\\ & VYWZV,& i_2{R}_2-i_4{R}_4+i_5{R}_5+i_7{R}_7& =0.\end{array}$$

再由再由四个顶点, 列出下面公式:

$$\begin{array}{lllc}& X,& i_0-i_1& =0,\\ & V,& i_1-i_2-i_3+i_5& =0,\\ & W,& i_3-i_4-i_7& =0,\\ & Z,& i_5-i_6-i_7& =0.\end{array}$$

联立即得.

2.4 最小生成树

最小连接问题

交通网络中, 常常关注能把所有站点连接起来的生成树, 使得该生成树各边权值之和为最小. 例如:

假设要在某地建造5个工厂, 拟修筑道路连接这5处. 经勘探, 其道路可按下图的无向边铺设. 现在每条边的长度已经测出并标记在图的对应边上, 如果我们要求铺设的道路总长度最短, 这样既能节省费用, 又能缩短工期 , 如何铺设？

不难发现: 最小代价的连接方式为:

最小连接问题的要求为:

• (1) 连接的边数最少(但图要连通);
• (2) 连接的边的总权值最小.

★最小生成树

连通赋权图中权值最小的生成树 (生成树中所有边权值的和) 称为最小生成树 (minimum spanning tree).

★Kruskal 算法

算法思想

从 $G$ 中的最小边开始, 避圈式的扩张.

算法复杂度

$O(n^2\log n)$

算法

(1) 选择边 $e_1$, 使得其权值最小;

(2) 若已经选定边 $e_1,e_2,\dots ,e_k$, 则从 $E-\{e_1,e_2,\dots ,e_k\}$ 中选择边 $e_{k+1}$ , 使得:

• a) $G[e_1,e_2,\dots ,e_{k+1}]$ 为无圈图;

• b) $e_{k+1}$ 的权值 $w(e_{k+1})$ 尽可能小.

(3) 当(2)不能进行时, 停止.

例

用 Kruskal 算法求下图的最小生成树.

解:

定理

由 Kruskal 算法得到的任何生成树一定是最小生成树.

(证明略)

例

在一个边赋权 $G$ 中, 下面算法是否可以产生有最小权值的生成路？为什么？

算法:

(1) 选一条边 $e_1$, 使得 $w(e_1)$ 尽可能小;

(2) 若边 $e_1,e_2,\dots ,e_i$ 已经选定, 则用下述方法从 $E-\{e_1,..,e_i\}$ 中选取边 $e_{i+1}$ 使得:

• a) $G[e_1,e_2,\dots ,e_i,e_{i+1}]$ 为不交路之并 (仅可能在路的端点相交);

• b) $w(e_{i+1})$ 是满足 a) 的尽可能小的权.

(3) 当 (2) 不能继续执行时停止.

解: 该方法不能得到一条最小生成路.

在下图 $G$ 中我们用算法求生成路:

用算法求出的生成路为:

直接在图中选出的一条生成路为:

后者的权值小于前者.

破圈法 (管梅谷)

在 Kruskal 算法基础上, 我国著名数学家山东师范大学管梅谷教授于 1975 年提出了最小生成树的破圈法.

算法

破圈法求最小生成树的求解过程是:

从赋权图 $G$ 的任意圈开始, 去掉该圈中权值最大的一条边, 称为破圈. 不断破圈, 直到 $G$ 中没有圈为止, 最后剩下的 $G$ 的子图为 $G$ 的最小生成树.

例

用破圈法求下图 $G$ 的最小生成树.

解:

反馈点集

反馈点集 (Feedback Vertex Set) 问题:

• Instance (实例): 设 $G$ 是一个图, $k$ 是一个正整数.

• Question (问题): 是否存在一个大小不超过 $k$ 的顶点子集 $S$ 使得 $G-S$ 不包含圈?

对最大度不超过 $4$ 的图 $G$, 该问题是 NP-困难的.

Remark: 破圈法和反馈点集, 从外表上看类似, 一个删边, 一个删点, 都使得剩余图没有圈. 但问题的复杂度大相径庭(差之毫厘, 谬以千里).

相关问题: 有向图的反馈点集和反馈弧 (有向边) 集问题都是 NP-完全的.

★Prim 算法

算法复杂度

$O(n^2\log n)$

算法

对于连通赋权图 $G$ 的任意一个顶点 $u$, 选择与点 $u$ 关联的且权值最小的边作为最小生成树的第一条边 $e_1$;

在接下来的边 $e_2,e_3,\dots ,e_{n-1}$, 在与一条已经选取的边只有一个公共端点的所有边中, 选取权值最小的边.

例

用 Prim 算法求下图的最小生成树.

解:

最小生成树权值为: $w(T)=10$.

贪心算法

Remark: 本节讲的最小生成树的三个算法都是基于贪心算法 (greedy algorithm) 的思想设计的: 每一步选择局部最优, 从而期望得到全局最优的算法.

• 如果组合优化问题满足拟阵的结构, 那么可以用适当的贪心算法得到最优解. 如最小生成树的三个算法.

• 不满足拟阵的结构的问题, 贪心算法可能得不到最优解. 如旅行商问题(TSP), 该问题将在第四章中介绍.

拟阵 (matriod) 是对向量空间中线性无关这一概念的概括与归纳. 拟阵有许多等价的定义, 参见 https://en.wikipedia.org/wiki/Matroid

2.5 根树简介

计算机中数据结构常采用根树结构. 族谱图也是根树.

有向树

一棵树 $T$, 如果每条边都有一个方向, 称这种树为有向树 (directed tree).

对于 $T$ 的顶点 $v$ 来说, 以点 $v$ 为终点的边数称为点 $v$ 的入度 (indegree), 以点 $v$ 为起点的边数称为点 $v$ 的出度 (outdegree). 入度与出度之和称为点 $v$ 的度.

★根树

一棵非平凡的有向树 $T$, 如果恰有一个顶点的入度为 $0$, 而其余所有顶点的入度为 $1$, 这样的有向树称为根树 (rooted tree).

其中入度为 $0$ 的点称为树根 (root),
出度为 $0$ 的点称为树叶 (leaf),
入度为 $1$, 出度大于等于 $1$ 的点称为内点 (internal vertex).

又将内点和树根统称为分支点 (branch vertex).

注: 根树常画成倒置形式, 方向由上指向下.

层数, 树高

对于根树 $T$, 顶点 $v$ 到树根的距离称为点 $v$ 的层数 (level).

所有顶点中的层数的最大者称为根树 $T$ 的树高 (height).

上图中, 根树高为 $3$ (树根1: 0层; 点2, 3, 4: 第1层; 余类推).

有序树

对于根树 $T$, 若规定了每层顶点的访问次序, 这样的根树称为有序树.

注: 一般次序为从左至右. 有时也用边的次序代替顶点次序.

子根树

对于根树 $T$, 由点 $v$ 及其 $v$ 的后代导出的子图, 称为根树的子根树 (sub-rooted tree).

★ $m$ 元根树, 完全 $m$ 元树

对于根树 $T$, 若每个分支点至多 $m$ 个儿子, 称该根树为 $m$ 元根树 ($m$-ary rooted tree); 若每个分支点恰有 $m$ 个儿子, 称它为完全 $m$ 元树 (complete $m$-ary rooted tree).

★定理

对于完全 $m$ 元树 $T$, 有如下性质:

在完全 $m$ 元树 $T$ 中, 若树叶数为 $t$, 分支点数为 $i$, 则:

$$(m-1)i=t-1$$

证明: 一方面, 由树的性质得:

$$m(T)=(i+t)-1\text{\hspace{1em}(1)}$$

另一方面, 由握手定理得:

$$2m(T)=t+m+(i-1)(m+1)\text{\hspace{1em}(2)}$$

由 (1) 与 (2) 消去 $m(T)$ 得:

$$(m-1)i=t-1$$

例

一台计算机, 它有一条加法指令, 可以计算 $3$ 个数的和. 如果要求 $9$ 个数的和, 问至少执行多少次加法指令?

解: 用 $3$ 个顶点表示 $3$ 个数, 用一个父结点表示 $3$ 个数的和. 问题转化为求一棵有 $9$ 个叶点的完全 $3$ 元树的分支点数. 即: $m=3,t=9$, 求 $i$.

由定理得: $(3-1)i=9-1$.

$i=4$, 至少要执行 $4$ 次. 两种可能情况是:

赋权二元树

在m元树中, 应用最广泛的是二元树, 原因是它在计算机中容易处理.

设 $T$ 是一棵二元树, 若对所有 $t$ 片树叶赋权值 $w_i(1\le i\le t)$, 且权值为 $w_i$ 的树叶层数为 $L(w_i)$, 称:

$$W(T)=\sum _{i=1}^t{w}_{i}L(w_i)$$

为该赋权二元树的权 (weight).

★最优二元树

在所有赋权为 $w_i$ 的二元树中 $W(T)$ 最小的二元树称为最优二元树.

★哈夫曼算法

Huffman 算法 (亦称 Huffman 编码):

• (1) 初始: 令 $S=\{w_1,w_2,\dots ,w_i,\dots ,w_j,\dots ,w_t\}$;

• (2) 从 $S$ 中取出两个权值最小者 $w_i$ 与 $w_j$, 画结点 $v_i$, 带权 $w_i$, 画结点 $v_j$, 带权 $w_j$, 画 $v_i$ 与 $v_j$ 的父亲 $v$, 连接 $v_i$ 与 $v$, 连接 $v_j$ 与 $v$, 令 $v$ 带权 $w_i+w_j$;

• (3) 令 $S=(S-\{w_i,w_j\})\cup \{w_i+w_j\}$;

• (4) 判断 $S$ 是否只含一个元素, 若是, 停止, 否则转(2).

注:

• (1) 哈夫曼编码是前缀码, 因此是变长码, 不是纠错码;
• (2) 权一般代表发生的概率.

例

求带权为: 7, 8, 9, 12, 16的最优树.

解: 由哈夫曼算法:

$$\{7,8,9,12,16\}\Rightarrow \{9,12,15,16\}\Rightarrow \{15,16,21\}\Rightarrow \{21,31\}\Rightarrow \{52\}$$

无损数据压缩算法

RLE 算法

RLE算法 (Run Length Encoding): 把文件内容用”数据×重复次数”的形式来表示的压缩算法.

AAAAAABBCDDEEEEEF → A6B2C1D2E5F1

17个文字 (17字节) → 12个文字 (12字节)

Huffman 算法

用”二叉树”的形式实现哈夫曼编码的算法.

AAAAAABBCDDEEEEEF

实现: 出现频率越高的字符用尽可能少的位数来表示.

总位数$=4+4+3\ast 2+2\ast 2+2\ast 5+2\ast 6=40$ (5字节)