离散数学图论树

离散数学图论树第一页，共四十三页，编辑于2023年，星期一8.2

树树的术语起源于植物学和家谱学。早在1857年，英国数学ArthurCayley(1821—1895)就发现了树，当时他正在试图列举形为CnH2n+2的化合物的同分异构体。树具有广泛的应用，特别在计算机科学与管理科学中。如用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算机网络，用树模拟一系列决策完成的过程等。第二页，共四十三页，编辑于2023年，星期一8.2.1树的概念和基本性质在图论中：

1、连通的无环图称为树。2、除根之外，度＝1的顶点称为叶子，度＞1的顶点称为分支点或者内点。叶子分支点根第三页，共四十三页，编辑于2023年，星期一8.2.1树的概念和基本性质3、多个树称为森林；4、孤立顶点叫做平凡树。123456789101512131114平凡树第四页，共四十三页，编辑于2023年，星期一8.2.1树的概念和基本性质

[定理]T=(V,E)是结点数n=|V|1的树，则下述命题等价：（1）T是无回路的连通图；（2）T是连通的，且有n1条边；（3）T有n1条边，且T中无回路；（4）T的任意两点间有且只有唯一的通路；（5）T中无回路，但若在T的任一对不相邻的顶点之间增加一条边，则构成T中的唯一回路。第五页，共四十三页，编辑于2023年，星期一根树8.2.2几类常用树[有向树]

一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为一棵有向树，记为T。[根树]

一棵有向树T，若其中有且仅有一个结点v0的入度为0，其余结点的入度为1，则称T是一棵以v0为根的根树或外向树。其中出度为0的结点称为有根树的叶子。把外向树之定向反过来，得到的有向树叫内向树。

v0v0第六页，共四十三页，编辑于2023年，星期一8.2.2几类常用树根树通常画成倒长的；一个结点的子结点画在它的下一层，边的方向省略；“同辈兄弟”画在同一层。第七页，共四十三页，编辑于2023年，星期一8.2.2几类常用树[树的高度]

设有根树T=(V,A)，v0为树根。u

V的深度是从v0

开始到达u的有向路的长度，T的高度是从v0到T的叶子的最长路的长度。根结点深度为0，称为第0层；深度同为i的结点构成树的第i层；具有最大深度的结点的深度称为树的深度（高度）。第八页，共四十三页，编辑于2023年，星期一8.2.2几类常用树TreeNodeLevelandPathLength第九页，共四十三页，编辑于2023年，星期一8.2.2几类常用树有序树[定义]

对有向树T=(V,A)，若u,vV且<u,v>A，则称u为v的父亲，v为u的儿子。若从u到v存在有向道路，则称u是v的祖先，v是u的后代（子孙）[有序树]

将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。有序树的每个结点的出度小于或等于m时，称为m叉有序树。有序树的每个结点的出度只为0或m

时，称为m叉正则有序树。第十页，共四十三页，编辑于2023年，星期一8.2.2几类常用树例设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。a:b＜＞＝a:cc重c轻＜＞＝a:dd重全真d轻＜＞＝a:ca轻b重＜＝a:cb轻a重＞＝第十一页，共四十三页，编辑于2023年，星期一8.2.2几类常用树容易看出，上例中方法并不唯一。a,b:c,d＜＞＝a:c＜＞＝d:cc轻a重＞＝a:c＝＜全真d:cb重d轻＜＞＝a轻c重＜＝a:b＝a:bb轻d重＜第十二页，共四十三页，编辑于2023年，星期一8.2.2几类常用树三、最优二叉树[二叉树]

除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两个分别称为左右子树的二叉树构成。[二叉树的性质]第i层的结点数最多为2i；深度为k的二叉树最多有2k+1-1个结点；记二叉树出度为2的结点数目为n2，叶子数目为n0，则有：n0=n2+1多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。第十三页，共四十三页，编辑于2023年，星期一8.2.2几类常用树[满二叉树]

二叉树的每个结点的出度或者是0或者是2。满二叉树也称正则二叉树[完美二叉树]

满二叉树且所有结点在同一层。对完美二叉树的结点按从上到下，同层结点从左到右的原则编号，得到结点从1~2k+1-1的编号序列。得到上述结点编号的二叉树称为编号二叉树。[完全二叉树]若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。

。第十四页，共四十三页，编辑于2023年，星期一8.2.2几类常用树高度为k的完全二叉树，其k-1层以上结点构成一棵高度为k-1的完美二叉树。完全二叉树的叶结点或者在同一层或者在相邻的两层。1671213141511109584231211109876543211671415958423满二叉树完美二叉树完全二叉树第十五页，共四十三页，编辑于2023年，星期一8.2.2几类常用树三、最优二叉树[定义]设T是有t片叶子的二叉树，其中t片叶子分别带有非负实权，则称T为加权二叉树。称W(T)＝为二叉树T的权，其中hi为带权wi的树叶vi的层数。在所有的带权的二叉树中，带权最小的二叉树称为最优二叉树(哈夫曼树)第十六页，共四十三页，编辑于2023年，星期一8.2.2几类常用树【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：

(a)W(T)=7*2+5*2+2*2+4*2=36

(b)W(T)==7*3+5*3+2*1+4*2=46

(c)W(T)==7*1+5*2+2*3+4*3=35其中(c)树的W最小，它就是最优二叉树(哈夫曼树)。第十七页，共四十三页，编辑于2023年，星期一8.2.2几类常用树Huffman树[Huffman算法]

给定t个非负实数，构造以它们为叶子带权且具有最小M(T)的最优二叉树。it；若i=1结束；将i个非负实数权由小到大排列成序，以最小的两个数作为左右儿子，构造其父亲结点，并以此左右儿子的权值之和作为新构造的父亲结点的权值。在权序列中删去此左右儿子对应的权值，增加新构造的父亲结点的权值。

i

i-1，转(2)。第十八页，共四十三页，编辑于2023年，星期一8.2.2几类常用树例：有4个权值{7,5,2,4}，试构造一棵有4个叶子结点的哈夫曼树。第十九页，共四十三页，编辑于2023年，星期一8.2.2几类常用树[Huffman树]

由Huffman算法构造的二叉树称为相对于非负实数权wi(i=1,2,…,t)的Huffman树。[定理]Huffman树是一棵相对于非负实数权wi(i=1,2,…,t)的最优二叉树。第二十页，共四十三页，编辑于2023年，星期一8.2.2几类常用树定义：有一个序列的集合，如果在这个集合中。任何序列都不是另一个序列的前缀，则称这个集合为前缀码。例如，001是001011的前缀，集合{000,001,01,10,11}是前缀码，而{1,00,01,000,0001}不是前缀码。[二元前缀码]前缀码A={1,2,…,m

}中的i只由两种符号（如0、1）组成时，称A为一个二元前缀码。第二十一页，共四十三页，编辑于2023年，星期一8.2.2几类常用树对有序二叉树的顶点编码如下：(1)根不标码；(2)兄弟有序，左为兄，标0，右为弟，标1；(3)从根始到叶上的道路依次抄出各点之码，写在叶下方，称该叶的前缀；(4)全树的叶从左到有把它们的前缀依次抄出，叫做该树的前缀码，每个叶子的前缀后加逗号，最后一个叶子前缀后加句号。显然有序二叉树与前缀码一一对应。第二十二页，共四十三页，编辑于2023年，星期一8.2.2几类常用树例如，0000，0001，001，010，011，100，101，11这一前缀码对应的有序二叉树如下图所示：v0011010100101010000000100101001110010111第二十三页，共四十三页，编辑于2023年，星期一8.2.2几类常用树[Huffman编码]

以各个源码符号在源码电文中出现的频率为权值，构造以源码符号为叶子的Huffman树，得到关于源码符号集的一个二叉前缀码，称为其Huffman编码。[定理]Huffman编码是关于该源码符号集的最短二叉前缀码。[证明]

略第二十四页，共四十三页，编辑于2023年，星期一8.2.2几类常用树实现译文长度最短的二叉前缀码设计过程：字频统计等概率假设Huffman树构造Huffman编码方案确定[例]

设一段电文含有x1,x2,x3,x4,x5,x6,x7共7个符号，它们出现的频率分别是：x1:35%x2:20%x3:15%x4:10x5:10%x6:5%x7:5%。试为这7个符号设计一套最短二叉前缀编码方案。第二十五页，共四十三页，编辑于2023年，星期一8.2.2几类常用树例第二十六页，共四十三页，编辑于2023年，星期一8.2.2几类常用树Huffman树的用途很广：分支程序的判断流程：如果出现概率越大的分枝（条件语句）离根越近，那么所需执行的判断语句就越少，这样便可提高程序的执行效率；文件的压缩：根据文件中字符出现的频率，建成一棵Huffman树，出现次数越多的字符的Huffman编码越短，这样可以达到文件的压缩。第二十七页，共四十三页，编辑于2023年，星期一8.2.3生成树[生成树]如果一棵树T是图G的子图，则树T称为图G的生成树或支撑树；G－E(T)称为树T的余树，记作：T’；T’中的边称为图G的弦，也是树T的弦。1234567812345678余树弦第二十八页，共四十三页，编辑于2023年，星期一8.2.3生成树[定理]

任何连通图至少有一棵生成树。证明略[定理]

若连通图G=(V,E)，n=|V|，则图的生成树有n－1条边。用归纳法易证明。第二十九页，共四十三页，编辑于2023年，星期一8.3平面图

图的平面性问题，除了它的理论意义外，有许多实际应用。例如，单面印刷电路板和集成电路的布线问题。近年来，大规模集成电路的发展促进了图的平面性的研究。第三十页，共四十三页，编辑于2023年，星期一8.3.1平面图的定义

[可平面性]一个图G=(V,E)，若能将其画在平面上，且任意两条边的交点只能是G的顶点，则称G可嵌入平面，或称G是可平面的。可平面图在平面上的一个嵌入称为一个平面图。树是一类重要的平面图。应用举例：印刷电路版、集成电路设计。(a)(b)(c)(a)是可平面图，(b),(c)是(a)的平面嵌入，是平面图。第三十一页，共四十三页，编辑于2023年，星期一8.3.1平面图的定义[例]K5和K3,3是不可平面的。K5K3,3K5K3,3第三十二页，共四十三页，编辑于2023年，星期一8.3.1平面图的定义[区域]

由平面图的边包围而成，其中不含图的顶点。也称为面。包围域R的所有边组成的回路称为该域的边界，回路长度称为该域的度，记为deg(R)。v2R1R2R0v1v3v4v5v6v7各域的边界：R0:v1v2v4v5v7v7v4v3v1R1:v1v2v4v3v1R2:v4v5v7v4v6v4R3:v7v7[例]deg(R0)=8,deg(R1)=4,deg(R2)=5,deg(R3)=1R3第三十三页，共四十三页，编辑于2023年，星期一8.3.1平面图的定义[内部面和外部面]由平面图的边包围且无穷大的域称为外部面。（如上例的域R0为外部面）一个平面图有且只有一个外部面。[曲面嵌入]一个图可嵌入平面当且仅当它可嵌入曲面。[定理5-1-1]平面图G的所有域的度之和等于其边数m的2倍，即：第三十四页，共四十三页，编辑于2023年，星期一8.3.1平面图的定义显然：可平面图的子图仍然是可平面图；包含不可平面图的图是不可平面图；容易发现，平面图G每增加1条边，图G总的边数和面数都增加1。边界面第三十五页，共四十三页，编辑于2023年，星期一8.3.2欧拉公式

[定理欧拉公式]

（必要条件）

设平面连通图G有n个顶点，m条边，d个域，则有n-m+d=2。[证明]对m作归纳。m=0,m=1时成立。假定对于m=k成立:nk-mk+dk=2。当m=k+1时，考虑删除一条边后仍然连通的情况。(1)如果G有回路，则删除回路上一条边后的图边数减少一，面数减少一，故公式对G成立：nk-(mk+1)+(dk+1)=2.(2)G没有回路，只有割边，必有度数为一的结点，删除相应割边的一度顶点后，结点数和边数分别减少一，面数不变，故仍然有(nk+1)-(mk+1)+dk=2.欧拉公式对非简单图仍然成立。第三十六页，共四十三页，编辑于2023年，星期一8.3.2欧拉公式对于n个顶点，m条棱，d个面的凸多面体，n-m+d=2.[推论]

设平面图G的连通分支数为k，并有n个顶点，m条边，d个域，则有n-m+d=k+1。[证明]

对每个连通分支使用欧拉公式，注意它们共同拥有一个无穷面。[定理]

若图G是简单的平面图，则图G至少有一个顶点的度小于6。第三十七页，共四十三页，编辑于2023年，星期一8.3.3极大平面图[极大平面图]

设G=(V,E)为简单平面图，|V|3，若对任意vi,vjV，且(vi,vj)E，有G=(V,E{(vi,vj)})为非平面图，则称G为一个极大平面图。“极大性”乃针对固定顶点数的图的边的数目而言。第三十八页，共四十三页，编辑于2023年，星期一8.3.3极大平面图[极大平面图的性质]极大平面图是连通图。极大平面图的每个面都由3条边组成。极大平面图有3d=2m（d为面数目，m

为边数目）。[定理]

设极大平面图G有n个顶点，m条边，d个域，则有m=3n-6，d=2n-4。[证明]

将3d=2m代入欧拉公式。[推论]

简单平面图G有m

3n-6，d

2n-4。[定理]

简单平面图至少有一个顶点的度小于6。[证明]

设任一点的度6，得m3n，矛盾。第三十九页，共四十三页，编辑于2023年，星期一8.3.4