离散数学 图论树PPT课件

1、(5)G(5)G中没有回路，但在任何两个不同的顶点之间中没有回路，但在任何两个不同的顶点之间加一条新边加一条新边，在所得图，在所得图中得到惟一的一个含新边的中得到惟一的一个含新边的初级回路初级回路(6)G(6)G是连通的，但是连通的，但删去任何一条边删去任何一条边后，所得图后，所得图不连通不连通 G G连通：若存在二个结点无通路，则在二个结点添加边后不会出现回连通：若存在二个结点无通路，则在二个结点添加边后不会出现回路路3 3）树的性质）树的性质 对于给定的无向图对于给定的无向图树是树是边数最小的连通图边数最小的连通图（mn-1mn-1mn-1则有回路）则有回路） 结点的度：结点的度： d(v

2、i) = 2m =d(vi) = 2m =2(n-1)2(n-1) 定理：设定理：设T T是是n n阶非平凡的无向树，则阶非平凡的无向树，则T T中至少有中至少有 片树叶片树叶 设：有设：有x x片树叶，其余结点度数至少为片树叶，其余结点度数至少为2 2x + 2(n-x) = 2(n-1)x + 2(n-x) = 2(n-1) 例：无向树例：无向树T T中度为中度为4 4、3 3、2 2的结点各一个，其余为树叶，树叶？的结点各一个，其余为树叶，树叶？4+3+2+k = 2(3+k-1)4+3+2+k = 2(3+k-1)第1页/共31页4) 4) 阶数阶数n n比较小的所有非同构的无向树比较

3、小的所有非同构的无向树 例例1 1：画出：画出6 6阶所有阶所有非同构的无向树非同构的无向树 m=n-1=5 m=n-1=5 从树的节点之和来分析：结点之和为从树的节点之和来分析：结点之和为1010分配给分配给6 6个结点个结点 1 1 1 1 1 5 1 1 1 1 1 5 1 1 1 1 2 4 1 1 1 1 2 4 1 1 1 1 3 3 1 1 1 1 3 3 1 1 1 2 2 3 1 1 1 2 2 3 1 1 2 2 2 2 1 1 2 2 2 2例例2 2：7 7阶无向树中有阶无向树中有3 3片树叶和片树叶和1 1个个3 3度顶点，其余度顶点，其余3 3个顶点的度数均无个顶点

4、的度数均无1 1和和3 3试画出满足要求的所有非同构的无向树试画出满足要求的所有非同构的无向树 解答：从树的节点之和来分析：解答：从树的节点之和来分析：7 7阶无向阶无向树的边数树的边数m = m = （ ），）， 于是于是d(vi)d(vi)12123 33 + d(v5)+d(v6)+d(v7)3 + d(v5)+d(v6)+d(v7) 1 1 1 2 2 2 3 1 1 1 2 2 2 3 加入加入2 2，2 2，2 2 如何组成结点的度数序列使之如何组成结点的度数序列使之不同构不同构 主要分析：主要分析：度为度为3 3的结点的结点v v与其三个邻接点的关系与其三个邻接点的关系 邻接关系

5、不同就能得到不同构的树邻接关系不同就能得到不同构的树三个三个邻接邻接点度数：点度数：1 1 2 1 2 2 2 2 21 1 2 1 2 2 2 2 2第2页/共31页4 4）任何无向任何无向连通连通图图G G，都，都存在生成树存在生成树 无无向连通图向连通图G G的生成的生成树是树是不不唯一的唯一的第3页/共31页3 3、生成树的应用、生成树的应用 要建要建6 6个工厂，修建连接的通路（见图），为使个工厂，修建连接的通路（见图），为使5 5处都有路相通，处都有路相通，至少要建几条路？如何铺设？至少要建几条路？如何铺设？ 由于由于n=6 n=6 所以建所以建5 5条路即可条路即可 4 4、无向

6、图、无向图G G的生成树的确定：的生成树的确定： 二种方法：二种方法：1 1、破圈法破圈法：每次去掉回路中的一条边，：每次去掉回路中的一条边， 去掉总数为去掉总数为 m-n+1 m-n+1 条弦条弦 2 2、避圈法避圈法：由一个结点开始选一条边，：由一个结点开始选一条边， 逐渐添加与边关联的结点（只要不构成回路即逐渐添加与边关联的结点（只要不构成回路即可）可） 直到所有结点被添加，直到所有结点被添加，( (挑选挑选n-1n-1条边）条边）第4页/共31页3 3、带权图的最小生成树、带权图的最小生成树 (1) (1) 定义定义5 5 设无向连通带权图设无向连通带权图G GV W ，T T是是G

7、G的一棵生成树的一棵生成树 T T的各边权之和称为的各边权之和称为T T的的权权，记作，记作W(T)W(T)； G G的所有生成树中的所有生成树中权最小的生成树权最小的生成树称为称为G G的的最小生成树最小生成树。 (2) (2) 最小生成树的求法（这里介绍避圈法最小生成树的求法（这里介绍避圈法KruskalKruskal算法算法) ) 设设n n阶无向连通带权圈阶无向连通带权圈G GV E, W 有有m m条边，条边， 不妨设不妨设G G中没有环中没有环( (否则，可以将所有的环先删去否则，可以将所有的环先删去) )，将，将m m条边按权条边按权从小到大顺序排列，设为从小到大顺序排列，设为e

8、1,e2e1,e2，, ,emem； 取取e1e1在在T T中，然后依次检查中，然后依次检查e2e2，e3e3，emem. .若若ejej(j2)(j2)与已在与已在T T中的边中的边 不能构成回路，则取不能构成回路，则取ejej在在T T中，否则弃去中，否则弃去ejej； 算法停止时得到的算法停止时得到的T T为为G G的最小生成树。的最小生成树。 第5页/共31页避圈法避圈法KruskalKruskal算法算法(n-1(n-1次次) )1121241245(1)(2)(3)(4)第6页/共31页破圈法破圈法(1)512436(3)1245(2)12435第7页/共31页作业：作业：P319

9、 P319 习题十六习题十六 1 1、2 2、3 3、4 4、5 5、1313第8页/共31页16.3 16.3 根树及其应用根树及其应用有向树：有向树：设设D D是是有向图，有向图，若若D D的基图是的基图是无向树无向树， 则称则称D D为为有向树有向树. . 有向树中有向树中, ,根树最重要根树最重要, ,故只讨论根树故只讨论根树. .一、根树一、根树 1 1、定义：设、定义：设T T是是n(n2)n(n2)阶有向树阶有向树, ,若若T T中中有一个顶点有一个顶点的入度为的入度为0,0,其余顶点的入度均为其余顶点的入度均为1 1, ,则称则称T T为根树为根树。入度为入度为0 0的顶点称为

10、的顶点称为树根树根（相当于（相当于文件系统的盘文件系统的盘符符）入度为入度为1 1出度为出度为0 0的顶点称为的顶点称为树叶树叶（具体文件）。（具体文件）。入度为入度为1 1出度不为出度不为0 0的顶点称为的顶点称为内点内点（文件夹），（文件夹），内点和树根统称为内点和树根统称为分支结点分支结点第9页/共31页是否为根树是否为根树 (a) (b) (c) (a) (b) (c)(no) (no) (yes)(no) (no) (yes)第10页/共31页u从树根到从树根到T T的任意顶点的任意顶点v v的通路的通路( (路径路径) )长度称为长度称为v v的层的层数数。v5v5的层数为的层数为

11、 层。层。u层数最大顶点的层数称为层数最大顶点的层数称为树高树高将平凡树也称为根将平凡树也称为根树。树。u右右图中树高为（图中树高为（ ）。）。v1v2v3v4v5v6v7v8v9v10 在根树中，由于各有向边的方向是一在根树中，由于各有向边的方向是一致致的，的，所以画根树时可以省去各边上的所所以画根树时可以省去各边上的所有箭头，并将树根画在最上方有箭头，并将树根画在最上方第11页/共31页2 2、根树中顶点的关系、根树中顶点的关系 定义：设定义：设T T为一棵非平凡的根树，为一棵非平凡的根树，vi,vjVvi,vjV(T),(T),若若vivi可达可达vjvj, ,则称则称vivi为为vjv

12、j的的祖先祖先, ,vjvj为为vivi的的后代后代；若若vivi邻接到邻接到vjvj( (即即 E(T)E(T)，称称vivi为为vjvj的的父亲父亲, ,而而vjvj为为vivi的的儿儿子子若若vj,vkvj,vk的父亲相同，则称的父亲相同，则称vjvj与与vkvk是是兄弟兄弟v1v2v3v4v5v6v7v8v9v10v1v1为为v5v5的祖先的祖先,v5,v5为为v1v1的后代；的后代；v2v2为为v5v5的父亲的父亲, ,而而v5v5为为v2v2的儿子；的儿子；v4v4与与v5v5是兄弟是兄弟第12页/共31页3 3、有序树、有序树 设设T T为根树，若将为根树，若将T T中层数相同的

13、顶点都标定次中层数相同的顶点都标定次序，则称序，则称T T为为有序树有序树 根据根树根据根树T T中每个分支点中每个分支点儿子数儿子数以及以及是否有序是否有序，可以将根树分成下列各类：可以将根树分成下列各类： (1) (1)若若T T的每个分支点的每个分支点至多至多有有r r个儿子个儿子，则称，则称T T为为r r叉树叉树； 又若又若r r叉树是有序的，则称它为叉树是有序的，则称它为r r叉叉有序树有序树 (2)(2)若若T T的每个分支点都的每个分支点都恰好恰好有有r r个儿子个儿子，则称，则称T T为为r r叉叉正则树正则树； 又若又若T T是有序的，则称它为是有序的，则称它为r r叉正则

14、有序树叉正则有序树 (3)(3)若若T T是是r r叉正则树，且叉正则树，且每个树叶的层数均为树高每个树叶的层数均为树高，则称则称T T为为r r叉叉完全完全正则树正则树， 又若又若T T是有序的，则称它为是有序的，则称它为r r叉完全正则有序树叉完全正则有序树。第13页/共31页v1v2v3v4v5v6v7v8v9v10二叉二叉有序有序树树v1v2v3v4v5v6v7 v8 v9 v10 v11 v12 v13 v14 v15二叉二叉完全完全正则正则有序有序树树四叉树四叉树(a)(b)(c)第14页/共31页4 4、r r叉树的子树叉树的子树 定义：定义： 设设T T为一棵根树，为一棵根树，

15、v V(T)v V(T)， 称称v v及其后代的导出子图及其后代的导出子图TvTv为为T T的以的以v v为根的为根的根子根子树树 如：如：二二叉正则有序树的每个分支点的两个儿子导叉正则有序树的每个分支点的两个儿子导出的根子树分别称为出的根子树分别称为左子树左子树和和右子树右子树v1v2v3v4v5v6v7 v8 v9 v10 v11 v12 v13 v14 v15v2v4v5 v8 v9 v10 v11v3v6v7v12 v13 v14 v15左子树左子树右子树右子树第15页/共31页二、根树的应用二、根树的应用1 1、最优、最优二二叉树定义：设叉树定义：设二二叉树叉树T T有有t t片树叶

16、片树叶v1,v2,v1,v2, ,vtvt, ,权分别为权分别为w1,w2,w1,w2, ,wtwt, , 称称 W(T)W(T)wiwi |(vi) |(vi)为为T T的权的权，其中其中|(vi)|(vi)是是vivi的层数（也可以的层数（也可以是从根到该叶子的通路长度）是从根到该叶子的通路长度） 在所有有在所有有t t片树叶片树叶, ,带权带权w1,w2w1,w2，, ,wtwt的的二二叉树叉树中中, , 总权值总权值W(T)W(T)最小的最小的二二叉树称为叉树称为最优最优二二叉树叉树 三棵带权三棵带权二二叉树叉树W(T1)W(T1)2 2（2+2)+32+2)+3* *3+53+5*

17、*3+33+3* *2 23838W(T2)W(T2)4(3+5)+34(3+5)+3* *3+23+2* *2+22+24747W(T3)W(T3)3 3* *(3+3)+5(3+3)+5* *2+2(2+2)2+2(2+2)3636 第16页/共31页2.Huffman2.Huffman算法算法( (在给定权值下在给定权值下, ,如何构造最如何构造最优优二二叉树叉树) ) 给定实数给定实数( (权值权值) )：w1w1，w2w2，wtwt，按从小到大，按从小到大排序为排序为w1w2w1w2wt.wt.(1) (1) 连接权为连接权为w1,w2w1,w2的两片树叶的两片树叶, ,得一个分支点

18、得一个分支点, ,其权其权为为w1+w2w1+w2(2) (2) 在在w1+w2w1+w2，w3w3，w4w4，wtwt中选出两个权最小的，中选出两个权最小的，连接它们对应的顶点连接它们对应的顶点( (不一定是树叶不一定是树叶) )，得新分支点及，得新分支点及所带的权所带的权(3) (3) 重复重复(2),(2),直到形成直到形成t-1t-1个分支点个分支点,t,t片树叶为止片树叶为止例：例： 求求2 2，2 2，3 3，3 3，5 5的最优二叉树的最优二叉树第17页/共31页例：例： 求求2 2，2 2，3 3，3 3，5 5的最优二叉树的最优二叉树2 2 2 24 43 3 3 36 6(

19、2)(2) 3 3，3 3，4 4，5 5(1)(1) 2 2，2 2，3 3，3 3，5 5(3)(3) 4 4，5 5，6 69 95 5(4) 6(4) 6，9 915153 3 3 36 6最优二叉树总的原则是：权值较大的叶子距根较近，最优二叉树总的原则是：权值较大的叶子距根较近，权值较小的可以距根较远权值较小的可以距根较远例：给定一组权值例：给定一组权值3 3，5 5，6 6，9 9，1111，1414，1616，1818构造构造相应的最优二叉树相应的最优二叉树第18页/共31页3 3、前缀编码、前缀编码 在通信中，常用二进制编码表示符号在通信中，常用二进制编码表示符号 1 1）等长

20、编码与不等长编码：）等长编码与不等长编码： 不等长编码可以使总电文总长度较短不等长编码可以使总电文总长度较短 2 2）不等长编码中编码的问题：如何识别？）不等长编码中编码的问题：如何识别？ 3) 3) 前缀编码定义：设前缀编码定义：设a a1 1a a2 2，a an-1n-1a an n为长为为长为n n的符号串，的符号串， 称其子串称其子串a a1 1, a, a1 1a a2 2, , ， a a1 1a a2 2a an-1n-1分别为该符号串的分别为该符号串的 长度为长度为1 1， 2 2， ， n-1n-1的前缀的前缀 设设A Abb1 1，b b2 2，b bm m 为一个符号串

21、集合，若对于任意的为一个符号串集合，若对于任意的b bi i，b bj jA (i j) A (i j) b bi i与与b bj j互不为前缀互不为前缀，则称，则称A A为为前缀码前缀码 若符号串若符号串b bi i(i(i1 1，2 2，m)m)中只出现中只出现0 0，1 1两个符号，则两个符号，则称称A A为为二元前缀码二元前缀码 1 1，1 10 0，10101 1，01010101，1011010 0，01000100，010001001 1 不是前缀码不是前缀码 11，0000，011011，01010101，0100101001，01000 01000 为前缀码为前缀码 1 1，

22、0101，1 11111，1 1100100，01011111 不是前缀码不是前缀码1, 10, 01, 101, 0101a, b, c , d , e第19页/共31页2 2）利用二叉树产生二元前缀码）利用二叉树产生二元前缀码 规定二叉树的左子树的边为规定二叉树的左子树的边为0 0，右子树的边为，右子树的边为1 1 则将从根到叶子结点的通路中边的序列即为叶则将从根到叶子结点的通路中边的序列即为叶子的子的二元前缀编码二元前缀编码111110000abcdea: 00b: 010c: 011d: 10e: 111第20页/共31页 通信中，每个字符出现的频率不同，如何使通信中，每个字符出现的频

23、率不同，如何使得传输效率最高？得传输效率最高？ 等长的编码一定不是最好的，考虑利用二元前缀等长的编码一定不是最好的，考虑利用二元前缀码。码。3 3）最优二元前缀码最优二元前缀码 给定所需编码的字符的频率给定所需编码的字符的频率, ,构造字符的二元构造字符的二元前缀编码，使其总电文长度为最短称为最优二前缀编码，使其总电文长度为最短称为最优二元前缀码。元前缀码。 先利用哈夫曼算法，生成先利用哈夫曼算法，生成最优二叉树最优二叉树； 再得到最优二元前缀码再得到最优二元前缀码第21页/共31页例：传输例：传输100100个八进制的数字，其出现的频率分别个八进制的数字，其出现的频率分别为：为：0-25%0

24、-25%， 1-20%1-20%， 2-15%2-15%， 3-10%3-10%， 4-10%4-10%， 5-10%5-10%， 6-5%6-5%， 7-5%7-5%。用用最优二元前缀码传输需要多少二进制数字？最优二元前缀码传输需要多少二进制数字？用等长用等长码传输需要多少二进制数字？码传输需要多少二进制数字？先得到先得到最优二元前缀码最优二元前缀码利用哈夫曼算法，利用哈夫曼算法，生成最优二叉树，生成最优二叉树，以频率为权值，以频率为权值，5,5,10,10,10,15,20,255,5,10,10,10,15,20,256,7,3, 4, 5, 2, 1, 06,7,3, 4, 5, 2,

25、 1, 06 67 73 4 5 2 13 4 5 2 10 0第22页/共31页5,5,10,10,10,15,20,255,5,10,10,10,15,20,256,7,3, 4, 5, 2, 1, 06,7,3, 4, 5, 2, 1, 0编码：编码：6-00006-0000；7-00017-0001；3-0013-001；4-0104-010；5-0115-011；2-1002-100；1-101,0-111-101,0-116 67 73 4 5 2 13 4 5 2 10 0总权总权值值: :（100100个字符的个字符的bitbit数）数） W(T)=(5+5) W(T)=(5+

26、5)* *4+(10+10+10+15+20)4+(10+10+10+15+20)* *3+253+25* *2=2852=285等长码：等长码：0-0000-000；1-0011-001；2-0102-010；3-0113-011；4-1004-100；5-1015-101；6-1106-110；7-111.7-111.总权值总权值: W2=3: W2=3* *100=300100=300第23页/共31页4 4、二叉树的周游（遍历）、二叉树的周游（遍历） 二叉树的周游：对于一棵二叉树的每一个结点都访问一二叉树的周游：对于一棵二叉树的每一个结点都访问一次且仅一次的操作次且仅一次的操作 1 1

27、）做一条绕行整个二叉树的行走路线（不能穿过树枝）做一条绕行整个二叉树的行走路线（不能穿过树枝） 2 2）按行走路线经过结点的位置（左边、下边、右边）按行走路线经过结点的位置（左边、下边、右边） 得到周游的方法有三种：得到周游的方法有三种：中序遍历（路线经过结点下边时访问结点）中序遍历（路线经过结点下边时访问结点） 访问的次序：左子树访问的次序：左子树根根右子树右子树前序遍历（路线经过结点左边时访问结点）前序遍历（路线经过结点左边时访问结点） 访问的次序：访问的次序：根根左子树右子树左子树右子树后序遍历（路线经过结点右边时访问结点）后序遍历（路线经过结点右边时访问结点） 访问的次序：左子树右子树

28、访问的次序：左子树右子树根根第24页/共31页abcdefghijk中序遍历（次序：左中序遍历（次序：左根根右右) )前序遍历（次序：前序遍历（次序：根根左右左右) )后序遍历（次序：左右后序遍历（次序：左右根根) )中序遍历中序遍历: :c b e d g f c b e d g f a a I k h j I k h j前序遍历前序遍历: :a b c d e f g h a b c d e f g h i i k j k j后序遍历后序遍历: :c e g f d b k c e g f d b k i i j h a j h a例：给定二叉树，写出三种访问例：给定二叉树，写出三种访问结点的序列结点的序列例：给定二叉树周游的二种周游例：给定二叉树周游的二种周游序列，画出该二叉树序列，画出该二叉树第25页/共31页5 5、二叉排序树、二叉排序树 将一组需要排序的序列建立二叉排序树将一组需要排序的序列建立二叉排序树 建立（不断添加结点为其子树：建立（不断添加结点为其子树： 比根结点小的为左子树比根结点