第三章树3.1树的有关定义

第三章树

3.1树的有关定义给定一个图，如果它不含任何回路，我们就叫它是林，如果又是连通的，即这个林只有一个连通支，就称它是树。树的有关定义定义3.1.1

一个不含任何回路的连通图称为树，用表示。中的边称为树支，度为1的节点称为树叶。树的每条边，都不会属于任何回路。这样的边叫割边。树的有关定义定义3.1.2

设是的一条边，若比的连通支树连通支数增加，则称是的一条割边。显然，图删去割边之后，结点分属于不同的分支。树的有关定义定理3.1.1

是割边，当且仅当不属于的任何回路。证明：若属于的某个回路，则中仍存在到的道路，故结点和属于同一连通支，不是割边。反之，若不是割边，则与的连通支数一样。于是和仍属于同一连同支，故中存在道路就是的一个回路。树的有关定义定理3.1.2

设是结点数为的树，则下列性质等价：连通且无回路连通且每条都是割边连通且有条边有条边且无回路的任意两结点间有唯一道路无回路,但在任两结点间加上一条边后恰有一个回路树的有关定义定理3.1.3

树中一定存在树叶结点。证明：由于是连通图，所以任一结点，都有。若无树叶，则。这样矛盾。定义3.1.3

如果是图的支撑子图,而且又是一棵树,则称是的一棵支撑树,或称生成树,又简称的树。3.6Huffman树定义3.6.1

除树叶外，其余结点的正度最多为2的外向树称为二叉树。如果它们的正度都是2，称为完全二叉树。Huffman树定义3.6.1

如果二叉树T的每个树叶结点vi都分别赋以一个正实数wi，则称T是赋权二叉树。从根v0到树叶vi的路径P(v0,vi)所包含的边数计为该路径的长度li，这样二叉树的路径总长是

vi是树叶如果给定了树叶数目以及它们的权值，可以构造许多不同的赋权二叉树，在这些赋权二叉树中，必定存在路径总长WPL最小的二叉树，这样的树称为最优二叉树。Huffman树例3.6.1

已知英文字符串adacatedecade。试用二进制字符串代替某个字幕，并保证该英文字符串与二进制串构成一一对应。解：该字符串中有字母a,d,e,c,t，它们分别出现4,3,3,2,1次。令每个字母对应二叉树的一个树叶，根到树叶的路径是唯一的，而且这条路径决不会是根到另一个树叶路径的一部分。这样跟到树叶的路径与该字母构成一一对应。如果在树T中令向左的边为0，向右的边为1，那么这些路径又与二进制串构成了一一对应。Huffman树哈夫曼给出了一个计算Huffman树算法：对个权值进行排序，满足计算作为中间结点的权，的左儿子是，右儿子是。在权序列中删去和，加入。若，否则转(1)。

Huffman树Huffman树算法的计算复杂度是O(nlogn)。

Huffman树定理3.6.1

由Huffman算法得到的二叉树是最优二叉树3.7最短树3.7.1Kruskal算法

Kruskal算法的描述如下：

T←Φ，当|T|<n–1且E≠Φ时,begine←E中最短边.E←E-e.若T+e无回路,则T←T+e.end

若|T|<n-1打印”非连通”,否则输出最短树最短树定理3.7.1

是赋权连通图的最短树，当且仅当对任意的余树边，回路满足其边权

证明:必要性，如果存在一条余树边，满足

,则得到新树比更加短,与是最短树矛盾。最短树充分性，若存在比还短的树,则，设

则构成唯一回路。如果对任意的关于的余树边，它与回路里的树支边都有，则，与假设矛盾.因此一定存在某边，对于某条边，满足。

最短树定理

3.7.2Kruskal算法的计算复杂性是，其中是迭代次数。最短树3.7.2Prim算法

Prim算法的基本思想是：首先任选一结点构成集合，然后不断在中选一条到中某点(比如)最短的边进入树，并且，直到。最短树Prim算法的描述如下:

WhileU≠Vdobegin

ForvV-Udoend最短树定理3.7.3

设是赋权连通图的结点真子集，是二端点分跨在和的最短边，则中一定存在包含的最短树干。证明：设是的一棵最短树，若，则构成唯一回路。该回路一定包含和其中，。由以知条件，作得到的仍是最短树。最短树定理3.7.4

Prim算法的结果是一得到赋权连通图的一棵最短树。证明：首先证明它是一棵支撑树。采用归纳法，初始，它是由导出的树，设是导出的树，则下一次迭代时，中增加一新结点中也加入一条与相连的边，因是连通的，则有