《第三章树3.1树的有关定义》由会员分享，可在线阅读，更多相关《第三章树3.1树的有关定义（21页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章 树树3.1 树的有关定义树的有关定义l给定一个图 ，如果它不含任何回路，我们就叫它是林，如果 又是连通的，即这个林只有一个连通支，就称它是树。树的有关定义树的有关定义l定义3.1.1 一个不含任何回路的连通图称为树，用 表示。 中的边称为树支，度为1的节点称为树叶。 树的每条边，都不会属于任何回路。这样的边叫割边。树的有关定义树的有关定义l定义3.1.2 设 是 的一条边，若 比 的连通支树连通支数增加，则称 是 的一条割边。 显然，图 删去割边 之后，结点 分属于不同的分支。树的有关定义树的有关定义l定理3.1.1 是割边，当且仅当 不属于 的任何回路。 证明：若 属于 的某个
2、回路，则 中仍存在 到 的道路，故结点 和 属于同一连通支， 不是割边。反之，若 不是割边，则 与 的连通支数一样。于是 和 仍属于同一连同支，故 中存在道路 就是 的一个回路。树的有关定义树的有关定义l定理3.1.2 设 是结点数为 的树，则下列性质等价：1. 连通且无回路2. 连通且每条都是割边3. 连通且有 条边4. 有 条边且无回路5. 的任意两结点间有唯一道路6. 无回路,但在任两结点间加上一条边后恰有一个回路树的有关定义树的有关定义l定理3.1.3 树 中一定存在树叶结点。 证明：由于 是连通图，所以任一结点 ，都有 。若无树叶，则 。 这样 矛盾。l定义3.1.3 如果 是图 的
3、支撑子图,而且又是一棵树,则称 是 的一棵支撑树,或称生成树,又简称 的树。3.6 Huffman树树l定义3.6.1 除树叶外，其余结点的正度最多为2的外向树称为二叉树。如果它们的正度都是2，称为完全二叉树。Huffman树树l定义3.6.1 如果二叉树T的每个树叶结点vi都分别赋以一个正实数wi，则称T是赋权二叉树。从根v0到树叶vi的路径P(v0,vi)所包含的边数计为该路径的长度li，这样二叉树的路径总长是 vi是树叶 如果给定了树叶数目以及它们的权值，可以构造许多不同的赋权二叉树，在这些赋权二叉树中，必定存在路径总长WPL最小的二叉树，这样的树称为最优二叉树。Huffman树树l例3
4、.6.1 已知英文字符串adacatedecade。试用二进制字符串代替某个字幕，并保证该英文字符串与二进制串构成一一对应。解：该字符串中有字母a,d,e,c,t，它们分别出现4,3,3,2,1次。令每个字母对应二叉树的一个树叶，根到树叶的路径是唯一的，而且这条路径决不会是根到另一个树叶路径的一部分。这样跟到树叶的路径与该字母构成一一对应。如果在树T中令向左的边为0，向右的边为1，那么这些路径又与二进制串构成了一一对应。Huffman树树l哈夫曼给出了一个计算Huffman树算法：1.对 个权值进行排序，满足2.计算 作为中间结点 的权， 的左儿子是 ，右儿子是 。在权序列中删去 和 ，加入
5、。若 ，否则转(1)。 Huffman树树lHuffman树算法的计算复杂度是O(n log n)。 Huffman树树l定理3.6.1 由Huffman算法得到的二叉树是最优二叉树3.7 最短树最短树l3.7.1 Kruskal算法 Kruskal算法的描述如下： T， 当|T| n 1且E时, begin1.eE中最短边.2.EE-e.3.若T+e无回路,则TT+e. end 若|T|n-1打印”非连通”,否则输出最短树最短树最短树l定理 3.7.1 是赋权连通图 的最短树，当且仅当对任意的余树边 ，回路 满足其边权 证明:必要性，如果存在一条余树边 ，满足 ,则 得到新树 比 更加短,与
6、 是最短树矛盾。最短树最短树l充分性，若存在比 还短的树 ,则 ，设 则 构成唯一回路 。如果对任意的 关于 的余树边 ，它与回路 里的树支边 都有 ，则 ，与假设矛盾.因此一定存在某边 ，对于某条边 ， 满足 。 最短树最短树l定理 3.7.2 Kruskal算法的计算复杂性是 ，其中是迭代次数。最短树最短树l3.7.2 Prim算法Prim算法的基本思想是：首先任选一结点 构成集合 ，然后不断在 中选一条到 中某点(比如 )最短的边 进入树 ，并且 ，直到 。最短树最短树lPrim算法的描述如下:1. 2.While UV do begin3. 4. 5. 6.For v V-U do e
7、nd最短树最短树l定理 3.7.3 设 是赋权连通图 的结点真子集， 是二端点分跨在 和 的最短边，则 中一定存在包含 的最短树干。 证明：设 是 的一棵最短树，若 ，则 构成唯一回路。该回路一定包含 和 其中 ， 。由以知条件 ，作 得到的仍是最短树。最短树最短树l定理 3.7.4Prim算法的结果是一得到赋权连通图 的一棵最短树。 证明：首先证明它是一棵支撑树。采用归纳法，初始 ，它是由 导出的树，设 是 导出的树，则下一次迭代时， 中增加一新结点 中也加入一条与 相连的边，因 是连通的，则有 条边,它是由 导出的一棵树。因此最终 是 的支撑树。最短树最短树l以下再证 是一棵最短树 设 是 的一棵最短树， ，由定理3.7.3，对任意的 ，一定有最短树 ，其中 。继续对 如此处理，直到最终 它仍然是最短树。
