第16章树离散数学

在离散数学中，图是一个由点和边组成的抽象数学模型。

其中，树是一种特殊的图，它是一个无环连通图。

在图论中，树扮演了重要的角色，它具有许多有趣的性质和应用。

而生成树则是树的一个特殊子集，它由给定图中的所有顶点和部分边构成。

本文将介绍图的树的基本概念，并探讨生成树的计数方法。

首先，让我们来看看图的树。

树是一种无环连通图，其中任意两个顶点之间存在唯一一条路径。

它具有以下性质：1.n个顶点的树有n-1条边。

这可以通过归纳法证明：当n=1时，结论成立；假设n=k时成立，那么n=k+1时，只需要添加一个顶点和一条边，即可构成n=k+1个顶点的树。

因此，结论成立。

2.连接树上任意两个顶点的边都是桥。

即如果一条边被删除，那么树就会变成两个或更多个不相连的子树。

3.树是一个高度平衡的结构。

对于一个n个顶点的树，任意两个叶子结点之间的路径长度至多相差1。

4.树的任意两个顶点之间有唯一一条路径，路径长度为顶点之间的边数。

接下来，让我们来讨论生成树的计数方法。

生成树是树的一个特殊子集，它是由给定图中的所有顶点和部分边构成。

生成树的计数在图论中具有重要的意义和应用。

对于一个具有n个顶点的连通图来说，其生成树的个数可以通过Cayley公式计算得到。

Cayley公式是由亚瑟·凯利于1889年提出的，它给出了完全图的生成树数目。

据此，我们可以得到生成树的计数公式为：T = n^(n-2)，其中T表示生成树的个数。

此外，还有一种常见的计数方法是基于度数矩阵和邻接矩阵的矩阵树定理。

矩阵树定理由高斯于1847年提出，它提供了一种计算图的生成树个数的方法。

根据矩阵树定理，一个无向图G的生成树数目等于该图度数矩阵的任意一个(n-1)阶主子式的行列式的值。

其中，度数矩阵是一个对角矩阵，它的对角线上的元素为各个顶点的度数。

邻接矩阵则是一个关于顶点间连接关系的矩阵，其中1表示相邻顶点之间存在边，0表示不存在边。

除了数学方法，还存在一种基于图的遍历的计数方法，称为Kirchhoff矩阵树定理。

二叉树
• 定义:二元有序树称为二叉树.
– 每个顶点最多有两个子顶点,一般称为左子顶 点和右子顶点. – 类似地,称每个顶点的左子树和右子树. – 每个顶点的出度都是0或2,称为二叉正则树.
二叉树的性质
• 定理:设有二叉树T, (1)第i层最多有2i个顶点; (2)若T高度为h,则T最多有2h11个顶点，最 少有h个顶点; (3)树叶个数出度为2的顶点个数1.
1 2
Huffman树与最优编码
• 若以符号为树叶,符号概率为树叶的权,利 用通过Huffman算法得到的二叉树对符号 编码,则可以保证i pili最小. • 例:对1,1,2,3,5,6,7,8构造Huffman树.
7 3 2 1 1 5 6
8
编码：设 A, B, C, D 的频率（即权值）分别为 17％, 25％, 38％, 20％， 试设计哈夫曼编码（最佳前缀码/最优编码）。
最优编码
• 构成消息的各符号的使用频率是不一样 的,显然常用符号编码短一些,罕用符号编 码长一点,可以使传输的二进制位数最少. • 最优编码问题:给定符号集{a1,a2,...,am}, ai 的出现概率是pi,编码长度为li,要使i pili最 小.
例：如果需传送的电文为 ‘A B A C C D A’，它只用到四种字符， 用两位二进制编码便可分辨。假设 A, B, C, D 的编码分别为 00， 01，10，11，则上述电文便为 ‘00010010101100’（共 14 位）， 译码员按两位进行分组译码，便可恢复原来的电文。 数据的最小冗余编码问题 在编码过程通常要考虑两个问题 译码的惟一性问题
5 1 5 6 6
U 1
1 5 6 1 5 5 4 6 5 4 5 5
2

在离散数学中，生成树（Spanning Tree）是一个图（Graph）的子图，它包含图中的所有顶点，并且是一个树（Tree）。

生成树的一个重要性质是它不包含任何环（Cycle）。

求一个给定图的生成树个数是一个经典问题，通常使用矩阵树定理（Matrix Tree Theorem）来解决。

矩阵树定理给出了一个图的生成树个数的计算公式，它基于图的拉普拉斯矩阵（Laplacian Matrix）的行列式。

拉普拉斯矩阵是一个方阵，其大小为图的顶点数，矩阵的元素定义如下：•如果i和j是不同的顶点，则矩阵的第i行第j列的元素是顶点i和j之间的边的权重（如果存在边的话），否则是0。

•对于每个顶点i，矩阵的第i行第i列的元素是顶点i的度（即与顶点i相邻的边的数量）的负值。

矩阵树定理指出，图的生成树个数等于其拉普拉斯矩阵的任何一个n-1阶主子式的行列式值的绝对值。

n是图的顶点数，n-1阶主子式意味着去掉矩阵中的一行和一列后得到的矩阵。

下面是一个简单的例子，说明如何使用矩阵树定理计算生成树的个数：假设有一个包含4个顶点的简单图，其边和权重如下：A -- 2 -- B| |1 3 1| |C -- 4 -- D1 -3 1 00 1 -3 40 0 1 -4主子式的行列式值。

去掉第一行和第一列后，我们得到：1 01 -3 40 1 -4x3矩阵的行列式，我们得到：1 * 1) - (0 * 0) = 12 - 1 = 11过程可能涉及复杂的行列式计算，特别是对于大型图来说。

在实际应用中，通常会使用专门的数学软件或库（如Python中的NumPy或SciPy）来进行这些计算。

此外，还有一些算法（如Kruskal算法和Prim算法）可以用来构造生成树，但它们并不直接计算生成树的总数。

这些算法通常用于找到图的一个生成树，而不是计算所有可能的生成树的数量。

中序遍历（次序：左－根－右) 前序遍历（次序：根－左－右) 后序遍历（次序：左－右－根) b 中序遍历: c b e d g f a I k h j 前序遍历: a b c d e f g h i k j 后序遍历: c e g f d b k i j h a
例：给定二叉树，写出三种访问 结点的序列
是否为根树
(a) (no)
(b) (no)
(c) (yes)
从树根到T的任意顶点v的通 路(路径)长度称为v的层数。 v5的层数为 层。
层数最大顶点的层数称为树 高．将平凡树也称为根树。 右图中树高为（ ）。
v1
v2 v3
v4 v8v5Fra bibliotekv6v7 v10
v9
在根树中，由于各有向边的方向是一 致的，所以画根树时可以省去各边上的所 有箭头，并将树根画在最上方．
等长码：0-000；1-001；2-010；3-011；4-100； 5-101；6-110；7-111. 总权值: W2=3*100=300
4、二叉树的周游（遍历）
二叉树的周游：对于一棵二叉树的每一个结点都访问一次且 仅一次的操作 1）做一条绕行整个二叉树的行走路线（不能穿过树枝） 2）按行走路线经过结点的位臵（左边、下边、右边） 得到周游的方法有三种： 中序遍历（路线经过结点下边时访问结点） 访问的次序：左子树－根－右子树 前序遍历（路线经过结点左边时访问结点） 访问的次序：根－左子树－右子树 后序遍历（路线经过结点右边时访问结点） 访问的次序：左子树－右子树－根
2、根树中顶点的关系
定义：设T为一棵非平凡的根树， v2 ∀vi,vj∈V(T),若vi可达vj,则称vi为 vj的祖先,vj为vi的后代； v4 v5 若vi邻接到vj(即<vi,vj>∈E(T)，称 vi为vj的父亲,而vj为vi的儿子 v8 若vj,vk的父亲相同，则称vj与vk是兄 弟