第二章 树与最优树¶
2.1 树的概念与性质¶
树与森林的概念¶
-
无圈图（acyclic graph）：不含圈的图称为无圈图。
-
树（tree）：树是连通的无圈图。
-
森林（forest）：无圈图 \(G\) 称为森林。
-
树与森林都是简单图；
-
树与森林都是偶图（二部图）。
-
-
平凡树与非平凡树：
-
平凡树：只有一个顶点的图/树（即阶为 \(1\) 的树）；
-
非平凡树：阶数大于等于 \(2\) 的树。
-
-
树叶与分支点：
-
树中度为 \(1\) 的顶点称为 树叶（leaf） 或悬挂点；
-
树中度大于 \(1\) 的顶点称为 分支点（branching vertex） 或内点。
-
树的性质¶
-
定理1：每棵非平凡树至少有两片树叶。
-
定理2：图 \(G\) 是树当且仅当 \(G\) 中任意两点都被唯一的路连接。
-
定理3：设 \(T\) 是 \((n,m)\) 树，则 \(m=n-1\)
-
该定理可通过对顶点数 \(n\) 作数学归纳法证明。
-
推论：具有 \(k\) 个分支的 \(n\) 阶森林有 \(n-k\) 条边。
-
-
定理4：每个 \(n\) 阶连通图的边数至少为 \(n-1\)。
- 当 \(G\) 是树时，边数恰为 \(n-1\)，因此树也被称为 最小连通图。
-
定理5：任意树 \(T\) 的两个不邻接顶点之间添加一条边后，可以得到唯一圈。
-
定理6：设 \(S=\{d_1,d_2,\ldots,d_n\}\) 是 \(n\) 个正整数序列，它们满足 \(d_1\geq d_2\geq\cdots\geq d_n\) 且 \(\sum_{i=1}^n d_i=2(n-1)\)，则存在一棵树 \(T\)，其度序列为 \(S\)。
树的中心与形心¶
-
图的顶点的离心率：顶点 \(v\) 到图中其余顶点的最大距离称为 \(v\) 的离心率，记作
\[ e(v)=\max\{d(u,v)\mid u\in V(G)\} \] -
图的直径：所有顶点离心率的最大值称为图的直径，即
\[ d(G)=\max\{e(v)\mid v\in V(G)\} \] -
图的半径：所有顶点离心率的最小值称为图的半径，记作
\[ r(G)=\min\{e(v)\mid v\in V(G)\} \] -
中心点与中心：
-
中心点：离心率等于半径的点，即满足 \(e(v)=r(G)\) 的顶点；
-
图的中心：全体中心点的集合。
- 每棵树的中心由一个点或两个相邻点组成。
-
-
树在顶点的分支：设 \(u\) 是树 \(T\) 的任意一个顶点，树 \(T\) 在顶点 \(u\) 的分支是指包含 \(u\) 作为一个叶点的极大子树，其分支数等于顶点 \(u\) 的度数；
-
顶点的权：树 \(T\) 在 \(u\) 点的分支中边的最大数目称为点 \(u\) 的权；
-
形心点与形心：
-
形心点：树 \(T\) 中权值最小的点称为它的一个形心点；
-
形心：全体形心点的集合。
-
2.2 生成树¶
生成树的概念与性质¶
-
生成树（spanning tree）：图 \(G\) 的一个生成子图 \(T\) 如果是树，称它为 \(G\) 的一棵生成树。
-
属于生成树 \(T\) 的边称为 \(G\) 关于 \(T\) 的 树枝；
-
属于 \(G\) 但不属于 \(T\) 的边称为 \(G\) 关于 \(T\) 的 弦/连枝。
-
-
生成森林（spanning forest）：若图 \(G\) 的生成子图为森林，称它为 \(G\) 的一个生成森林。
-
定理：每个连通图至少包含一棵生成树。
-
破圈法：若连通图 \(G\) 中有圈 \(C\)，去掉 \(C\) 中一条边后得到的图仍然连通，不断去掉图中的圈，最后得到一个无圈连通生成子图，即为 \(G\) 的一棵生成树。
-
连通图 \(G\) 的生成树一般不唯一。
-
生成树的计数¶
-
边的收缩（edge contraction）：称将 \(e\) 的两个端点合并为一个顶点，并删除所有与该顶点相连的自环边为边 \(e\) 的收缩，得到的图记为 \(G\cdot e\)。
-
凯莱递推计数法：设 \(e\) 是 \(G\) 的一条边，用 \(\tau(G)\) 表示 \(G\) 的生成树棵数，则有
\[ \tau(G)=\tau(G-e)+\tau(G\cdot e) \]-
包含边 \(e\) 的生成树棵数为 \(\tau(G\cdot e)\)；
-
不包含边 \(e\) 的生成树棵数为 \(\tau(G-e)\)。
-
缺点：递推计算量大，且不能具体指出每棵生成树。
-
-
矩阵树定理：给定图 \(G\)，设 \(A\) 是 \(G\) 的邻接矩阵，定义 \(n\) 阶方阵 \(C\)，其中：
\[ c_{ij}=\begin{cases}d(v_i),&i=j\\ -a_{ij},&i\neq j\end{cases} \]则 \(G\) 的生成树棵数等于 \(C\) 的任意一个余子式的值。
-
拉普拉斯矩阵：定理中的矩阵 \(C\) 又称为图的拉普拉斯矩阵（Laplacian matrix），可表示为
\[ C=D(G)-A(G) \]其中 \(D(G)\) 为顶点的度对角矩阵，\(A(G)\) 为邻接矩阵。
-
-
完全图的生成树数目（Cayley 公式）：\(n\) 阶完全图 \(K_n\) 的生成树棵数为
\[ \tau(K_n)=n^{n-2} \] -
删边完全图的生成树数目：若 \(e\) 为 \(K_n\) 的一条边，则有
\[ \tau(K_n-e)=(n-2)n^{n-3} \]
回路系统简介¶
-
连枝与树枝：设 \(T\) 是连通图 \(G\) 的一棵生成树
-
连枝：把属于 \(G\) 但不属于 \(T\) 的边称为 \(G\) 关于 \(T\) 的连枝；
-
树枝：把 \(T\) 中的边称为 \(G\) 关于 \(T\) 的树枝。
-
-
基本圈/基本回路：设 \(T\) 是连通图 \(G\) 的一棵生成树，由 \(G\) 对应于 \(T\) 的一条连枝与 \(T\) 中树枝构成的唯一圈 \(C\)，称为 \(G\) 关于 \(T\) 的一个基本圈或基本回路。
-
基本回路组：若 \(G\) 是 \((n,m)\) 连通图，把 \(G\) 对应于 \(T\) 的 \(m-n+1\) 个基本回路称为 \(G\) 对应于 \(T\) 的基本回路组，记为 \(C_f\)。
2.3 最小生成树¶
最小连接问题¶
-
最小生成树（minimum spanning tree）：连通边赋权图 \(G\) 中的各边权值之和最小的生成树，称为最小生成树或最小代价树。
-
常见的最小生成树算法包括：
-
克鲁斯克尔算法（Kruskal 算法）；
-
管梅谷的破圈法；
-
Prim 算法。
-
克鲁斯克尔算法（Kruskal 算法）¶
-
算法思想：从 \(G\) 中的最小边开始，进行避圈式扩张。
-
算法流程：
-
选择边 \(e_1\)，使得其权值最小；
-
若已经选定边 \(e_1,e_2,\ldots,e_k\)，则从 \(E\setminus\{e_1,e_2,\ldots,e_k\}\) 中选择边 \(e_{k+1}\)，使得：
-
\(G[\{e_1,e_2,\ldots,e_{k+1}\}]\) 为无圈图；
-
使 \(e_{k+1}\) 的权值尽可能小；
-
-
当选定 \(n-1\) 条边（步骤 2 不能继续进行）时停止。
-
-
由克鲁斯克尔算法得到的任何生成树一定是一棵最小生成树。
管梅谷的破圈法¶
-
算法流程：
-
从赋权图 \(G\) 的任意圈开始；
-
去掉该圈中权值最大的一条边（破圈）；
-
不断破圈，直到图 \(G\) 中没有圈为止；
-
最后剩下的 \(G\) 的生成子图即为 \(G\) 的最小生成树。
-
Prim 算法¶
-
算法流程：
-
对于连通赋权图 \(G\) 的任意一个顶点 \(u\)，选择与点 \(u\) 关联且权值最小的边作为最小生成树的第一条边 \(e_1\)；
-
若已选定边 \(e_1,e_2,\ldots,e_k\)，则从 \(E\setminus\{e_1,e_2,\ldots,e_k\}\) 中选择边 \(e_{k+1}\)，使得：
-
\(e_{k+1}\) 有且仅有一个顶点在边导出子图 \(G[\{e_1,e_2,\ldots,e_k\}]\) 中；
-
使 \(e_{k+1}\) 的权值尽可能小；
-
-
重复执行直至选满 \(n-1\) 条边。由反证法可证明 Prim 算法得到的生成树必为最小生成树。
-
计算机中的树简介¶
根树¶
-
根树（rooted tree）：一棵非平凡的有向树 \(T\)，如果恰有一个顶点的入度为 \(0\)，而其余所有顶点的入度均为 \(1\)，这样的有向树称为根树。
-
树根：入度为 \(0\) 的顶点；
-
树叶：出度为 \(0\) 的顶点；
-
内点：入度为 \(1\)、出度大于 \(1\) 的顶点；
-
分支点：内点和树根统称为分支点。
-
注：根树常画成倒置形式，方向由上指向下。
-
-
树的层数与树高：
-
层数：顶点 \(v\) 到树根的距离称为点 \(v\) 的层数（树根为 \(0\) 层）；
-
树高：所有顶点中层数的最大者称为根树 \(T\) 的树高。
-
-
有序树与子根树：
-
有序树：若规定了每层顶点的访问次序（一般次序为从左至右），这样的根树称为有序树；
-
子根树：由点 \(v\) 及其后代导出的子图称为根树的子根树。
-
\(k\) 元根树¶
-
\(k\) 元根树与完全 \(k\) 元树：
-
\(k\) 元根树：每个分支点至多有 \(k\) 个子节点的根树；
-
完全 \(k\) 元树：每个分支点恰有 \(k\) 个子节点的根树。
-
完全 \(k\) 元树性质：在完全 \(k\) 元树 \(T\) 中，若树叶数为 \(t\)，分支点数为 \(i\)，则
\[ (k-1)i=t-1 \]
-
二元树¶
-
二元树（binary tree）：即 \(2\) 元根树。
-
有序树转化为二元树的步骤：
-
从根开始，保留每个父节点同其最左子节点的连线，撤销与其他子节点的连线；
-
兄弟节点间用从左至右的有向边连接；
-
直接位于给定节点下方的子节点作为左子节点，同一下级水平线上与给定节点右邻的节点作为右子节点。
-
-
二元树的遍历：系统访问根节点使得每个节点恰好访问一次的常用方法：
-
先根次序遍历（先序遍历）：访问根 \(\to\) 按先根次序遍历根的左子树 \(\to\) 按先根次序遍历根的右子树（先左后右）；
-
中根次序遍历（中序遍历）：按中根次序遍历根的左子树 \(\to\) 访问根 \(\to\) 按中根次序遍历根的右子树；
-
后根次序遍历（后序遍历）：按后根次序遍历根的左子树 \(\to\) 按后根次序遍历根的右子树 \(\to\) 访问根。
-
-
二元树的权：设 \(T\) 是一棵二元树，若对所有 \(t\) 片树叶赋权值 \(w_i\)（\(1\leq i\leq t\)），且权值为 \(w_i\) 的树叶层数为 \(L(w_i)\)，称
\[ W(T)=\sum_{i=1}^t w_i L(w_i) \]为该赋权二元树的权。
-
最优二元树（哈夫曼树）：在所有赋权为 \(w_i\) 的二元树中，\(W(T)\) 最小的二元树称为最优二元树。
-
哈夫曼算法（Huffman 算法）：
-
初始：令集合 \(S=\{w_1,w_2,\ldots,w_t\}\)；
-
从 \(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\)；
-
令 \(S=(S\setminus\{w_i,w_j\})\cup\{w_i+w_j\}\)；
-
判断 \(S\) 是否只含一个元素，若是则停止，否则转步骤 2。
-