《《离散数学课件资料》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《离散数学课件资料》PPT课件.ppt（33页珍藏版）》请在金锄头文库上搜索。
1、8/19/20241离散数学树：树：树：树：连通而连通而连通而连通而不含回路不含回路不含回路不含回路的无向图称为的无向图称为的无向图称为的无向图称为无向树无向树无向树无向树，简称树简称树简称树简称树。 常记做常记做常记做常记做T T。树叶：树叶：树叶：树叶：树中度数为树中度数为树中度数为树中度数为1 1的结点。的结点。的结点。的结点。分支点：分支点：分支点：分支点：树中度数大于树中度数大于树中度数大于树中度数大于1 1的结点。的结点。的结点。的结点。森林：森林：森林：森林：连通分支数大于等于连通分支数大于等于连通分支数大于等于连通分支数大于等于2,2,2,2,且每个连通分支都是树的且每个连通分
2、支都是树的且每个连通分支都是树的且每个连通分支都是树的无向图。无向图。无向图。无向图。9.1 9.1 无向树及生成图无向树及生成图平凡树：平凡树：平凡树：平凡树：平凡图。平凡图。平凡图。平凡图。本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路本章所指回路为简单回路或初级回路8/19/20242离散数学8/19/20243离散数学一、无向树 (1) (1) G G连通且不含回路；连通且不含回路；连通且不含回路；连通且不含回路； (2) (2) G G中无回路，且中无回路，且中无回路，且中无回路，且mm = = n n-1-1，其中，其中，其中，其中
3、mm为边，为边，为边，为边， n n为结点数；为结点数；为结点数；为结点数； (3) (3) G G是连通的，且是连通的，且是连通的，且是连通的，且mm = = n n-1-1; ; ; ; (4) (4) G G中无回路，但在中无回路，但在中无回路，但在中无回路，但在G G中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路；条边，就得到唯一的一条初级回路； (5) (5) G G是连通的且是连通的且是连通的且是连通的且G G中每条边都是桥
4、；中每条边都是桥；中每条边都是桥；中每条边都是桥； (6) (6) G G中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。中每一对结点之间有唯一的一条基本通路。任意非平凡树任意非平凡树任意非平凡树任意非平凡树T (T (n n, , mm) )至少有两片树叶。至少有两片树叶。至少有两片树叶。至少有两片树叶。设设设设T T 有有有有k k片树叶，于是片树叶，于是片树叶，于是片树叶，于是2 2 m m k+ k+ 2 (2 (n n - - k k) )，则则则则2 (2 (n n-1) -1) 2 2n n - - k k，则，则
5、，则，则k k 2 28/19/20244离散数学例：例：画出画出6 6阶所有非同构的无向树。阶所有非同构的无向树。(1) 1，1，1，1，1，5(2) 1，1，1，1，2，4(3) 1，1，1，1，3，3(4) 1，1，1，2，2，3 两种两种(5) 1，1，2，2，2，2解：解：设设T是是6阶无向树，阶无向树，T的边数的边数m5 5，由由握手定理握手定理可知，可知，d( (v) )1010，且，且(T)1 1，(T)5 5。故故T T的度数列必为以下情况之一：的度数列必为以下情况之一：一、无向树8/19/20245离散数学8/19/20246离散数学二、生成树生成树：生成树：生成树：生成树
6、：若连通图若连通图若连通图若连通图G G的某个生成子图是一棵树，的某个生成子图是一棵树，的某个生成子图是一棵树，的某个生成子图是一棵树， 则称该树为则称该树为则称该树为则称该树为G G的生成树，记做的生成树，记做的生成树，记做的生成树，记做T TG G。树枝：树枝：树枝：树枝：生成树生成树生成树生成树T TG G的边。的边。的边。的边。弦：弦：弦：弦：G G中不在中不在中不在中不在T TG G中的边。中的边。中的边。中的边。生成树的余树生成树的余树生成树的余树生成树的余树( ( ( (补补补补) ) ) )：T TG G的所有弦的集合的导出的所有弦的集合的导出的所有弦的集合的导出的所有弦的集合
7、的导出子图。余树不一定是树子图。余树不一定是树子图。余树不一定是树子图。余树不一定是树, , , ,也不一定连通。也不一定连通。也不一定连通。也不一定连通。8/19/20247离散数学二、生成树d db ba ae ec cd db ba ae ec cb ba ae ec c图图图图G G生成树生成树生成树生成树T TG G生成树生成树生成树生成树T TG G的补的补的补的补无向连通图如果本身不是树，它的生成树是不唯一的，无向连通图如果本身不是树，它的生成树是不唯一的，无向连通图如果本身不是树，它的生成树是不唯一的，无向连通图如果本身不是树，它的生成树是不唯一的，但所有连通图都具有生成树。但
8、所有连通图都具有生成树。但所有连通图都具有生成树。但所有连通图都具有生成树。8/19/20248离散数学任何连通图任何连通图任何连通图任何连通图G G至少存在一棵生成树。至少存在一棵生成树。至少存在一棵生成树。至少存在一棵生成树。二、生成树8/19/20249离散数学二、生成树基本回路系统：基本回路系统：基本回路系统：基本回路系统： C C1 1, , C C2 2, , , , C Cmm n n+1+1 为为为为G G对应对应对应对应T T T T的的的的基本回路系统。基本回路系统。基本回路系统。基本回路系统。一个连通图对应不同的生成树的基本回一个连通图对应不同的生成树的基本回一个连通图对
9、应不同的生成树的基本回一个连通图对应不同的生成树的基本回路及路及路及路及基本回路基本回路基本回路基本回路系统可能不同，但是基本系统可能不同，但是基本系统可能不同，但是基本系统可能不同，但是基本回路的个数相等，等于回路的个数相等，等于回路的个数相等，等于回路的个数相等，等于mm n n+1+1。8/19/202410离散数学三、最小生成树最小生成树：最小生成树：最小生成树：最小生成树：设设设设G = G = 是无向是无向是无向是无向连通带权图，连通带权图，连通带权图，连通带权图，T T 是是是是G G 的一棵生成树，的一棵生成树，的一棵生成树，的一棵生成树，T T 各边带权之和称为各边带权之和称
10、为各边带权之和称为各边带权之和称为T T 的权，记为的权，记为的权，记为的权，记为WW( (T T) )。G G的所有生成树中带权最小的生成树称为的所有生成树中带权最小的生成树称为的所有生成树中带权最小的生成树称为的所有生成树中带权最小的生成树称为G G的最的最的最的最小生成树。小生成树。小生成树。小生成树。KruskalKruskal算法算法算法算法( (避圈法避圈法避圈法避圈法) )：设：设：设：设n n阶阶阶阶无向无向无向无向连通带权图连通带权图连通带权图连通带权图GG有有有有mm条边条边条边条边 ，它们带的权分别为，它们带的权分别为，它们带的权分别为，它们带的权分别为 ，设，设，设，设
11、 。 （1 1）取）取）取）取e e1 1在在在在T T中（中（中（中（ e e i非环，若是环，则放弃非环，若是环，则放弃）（2 2）若）若）若）若e e2 2不与不与不与不与e e1 1构成回路，取构成回路，取构成回路，取构成回路，取e e2 2在在在在T T中，否则放弃中，否则放弃中，否则放弃中，否则放弃e e2 2，考，考，考，考查查查查e e3 3，继续这一过程，直到形成生成树，继续这一过程，直到形成生成树，继续这一过程，直到形成生成树，继续这一过程，直到形成生成树T T为止。为止。为止。为止。8/19/202411离散数学abcdegf195141827168213ae12dcbg
12、f7148531621Kruskal算法算法: :71218198/19/202412离散数学9.2 9.2 根树及其应用根树及其应用其中：入度为其中：入度为其中：入度为其中：入度为0 0的顶点称为树根，的顶点称为树根，的顶点称为树根，的顶点称为树根，有向树有向树有向树有向树：一个有向图，若略去所有有向边的方向后得一个有向图，若略去所有有向边的方向后得一个有向图，若略去所有有向边的方向后得一个有向图，若略去所有有向边的方向后得到的无向图是一棵树，则称该有向图为有向树。到的无向图是一棵树，则称该有向图为有向树。到的无向图是一棵树，则称该有向图为有向树。到的无向图是一棵树，则称该有向图为有向树。根
13、树：根树：根树：根树：非平凡的有向树，若恰有一个结点的入度为非平凡的有向树，若恰有一个结点的入度为非平凡的有向树，若恰有一个结点的入度为非平凡的有向树，若恰有一个结点的入度为0 0， 其余所有顶点的入度均为其余所有顶点的入度均为其余所有顶点的入度均为其余所有顶点的入度均为1 1，则称此有向树为根树。，则称此有向树为根树。，则称此有向树为根树。，则称此有向树为根树。入度为入度为入度为入度为1 1，出度为，出度为，出度为，出度为0 0的顶点称为树叶，的顶点称为树叶，的顶点称为树叶，的顶点称为树叶，入度为入度为入度为入度为1 1出度大于出度大于出度大于出度大于0 0的顶点称为内点，的顶点称为内点，的
14、顶点称为内点，的顶点称为内点，内点和树根统称为分支点。内点和树根统称为分支点。内点和树根统称为分支点。内点和树根统称为分支点。8/19/202413离散数学一、有向树层数层数层数层数: :从树根到任意顶点从树根到任意顶点从树根到任意顶点从树根到任意顶点v v的通路长度，称为的通路长度，称为的通路长度，称为的通路长度，称为v v的层数，的层数，的层数，的层数，记为记为记为记为l l( (v v). ).树高树高树高树高: : : :层数最大的顶点的层数，记为层数最大的顶点的层数，记为层数最大的顶点的层数，记为层数最大的顶点的层数，记为h h(T(T) )。 （本书树根为第（本书树根为第（本书树根
15、为第（本书树根为第0 0 0 0层。）层。）层。）层。）8/19/202414离散数学根树根树根树根树可看成是可看成是可看成是可看成是家族树家族树家族树家族树：(1) (1) 若从若从若从若从a a到到到到b b可达，则称可达，则称可达，则称可达，则称a a是是是是b b的祖先，的祖先，的祖先，的祖先， b b是是是是a a的后代；的后代；的后代；的后代；(2) (2) 若若若若 是根树中的有向边，则称是根树中的有向边，则称是根树中的有向边，则称是根树中的有向边，则称a a是是是是b b的父亲，的父亲，的父亲，的父亲， b b是是是是a a的儿子；的儿子；的儿子；的儿子；(3) (3) 若若若
16、若b b、c c同为同为同为同为a a的儿子，则称的儿子，则称的儿子，则称的儿子，则称b b、c c为兄弟。为兄弟。为兄弟。为兄弟。一、有向树根子树根子树根子树根子树：根树根树根树根树T T 中，任一不为树根的顶点中，任一不为树根的顶点中，任一不为树根的顶点中，任一不为树根的顶点v v及其所有及其所有及其所有及其所有后代导出的子图后代导出的子图后代导出的子图后代导出的子图, , 称为称为称为称为T T 的以的以的以的以v v为根的子树。为根的子树。为根的子树。为根的子树。8/19/202415离散数学二、有序树r元树元树：每个分支点至多有：每个分支点至多有r个儿子；个儿子；r元有序树元有序树：
17、r元树是有序的；元树是有序的；r元正则树元正则树：每个分支点恰有：每个分支点恰有r个儿子；个儿子；r元正则有序树元正则有序树：r元正则树是有序的；元正则树是有序的；r元完全正则树元完全正则树：树叶层数均为树高的：树叶层数均为树高的r元正则树；元正则树；r元完全正则有序树元完全正则有序树：r元完全正则树是有序的。元完全正则树是有序的。有序树有序树有序树有序树：每层上的顶点都每层上的顶点都每层上的顶点都每层上的顶点都规定了规定了规定了规定了次序的根树。次序的根树。次序的根树。次序的根树。分类分类：根据根树根据根树T中每个分支点儿子数以及是否有序：中每个分支点儿子数以及是否有序：8/19/20241
18、6离散数学二、有序树将有序将有序将有序将有序树转换为二元树：树转换为二元树：树转换为二元树：树转换为二元树： (1) (1) 从树根开始，保留每个父亲顶点和最左边儿子从树根开始，保留每个父亲顶点和最左边儿子从树根开始，保留每个父亲顶点和最左边儿子从树根开始，保留每个父亲顶点和最左边儿子 的连线，撤消与其他儿子的连线；的连线，撤消与其他儿子的连线；的连线，撤消与其他儿子的连线；的连线，撤消与其他儿子的连线； (2) (2) 兄弟间用从左至右的水平有向边连接。兄弟间用从左至右的水平有向边连接。兄弟间用从左至右的水平有向边连接。兄弟间用从左至右的水平有向边连接。 (3) (3) 以位于给定顶点下面的
19、顶点作为以位于给定顶点下面的顶点作为以位于给定顶点下面的顶点作为以位于给定顶点下面的顶点作为左儿子左儿子左儿子左儿子，以给定，以给定，以给定，以给定 顶点的水平右邻顶点（顶点的水平右邻顶点（顶点的水平右邻顶点（顶点的水平右邻顶点（兄弟）兄弟）兄弟）兄弟）作为作为作为作为右儿子右儿子右儿子右儿子。将森林将森林将森林将森林转换为二元树：转换为二元树：转换为二元树：转换为二元树：将每棵树表示为二元树，除第一将每棵树表示为二元树，除第一将每棵树表示为二元树，除第一将每棵树表示为二元树，除第一棵二元树外，将余下每棵二元树作为前一棵二元树的根棵二元树外，将余下每棵二元树作为前一棵二元树的根棵二元树外，将余
20、下每棵二元树作为前一棵二元树的根棵二元树外，将余下每棵二元树作为前一棵二元树的根的右子树。的右子树。的右子树。的右子树。8/19/202417离散数学三、最优树带权二元树：带权二元树：带权二元树：带权二元树：设有一棵二元树有设有一棵二元树有设有一棵二元树有设有一棵二元树有t t 片树叶，分别带权为片树叶，分别带权为片树叶，分别带权为片树叶，分别带权为w w1 1、w w2 2 、 、w wt t，则称之为带权二元树；，则称之为带权二元树；，则称之为带权二元树；，则称之为带权二元树；权：权：权：权：称称称称 为该为该为该为该带权二元树的权带权二元树的权带权二元树的权带权二元树的权，其中，其中，其
21、中，其中，权为权为权为权为w wi i的树叶的层数为的树叶的层数为的树叶的层数为的树叶的层数为L L( (w wi i) ) ) )。 最优二元树：最优二元树：最优二元树：最优二元树：所有带权所有带权所有带权所有带权w w1 1、w w2 2 、 、w wt t的二元树中，的二元树中，的二元树中，的二元树中， 带权带权带权带权WW( ( T T) )最小的二元树。最小的二元树。最小的二元树。最小的二元树。8/19/202418离散数学例：下图所示的三棵例：下图所示的三棵二二叉树叉树T1,T2,T3都是带权为都是带权为2、2、3、3、5的的二二叉树叉树。 W(T1)=22+22+33+53+32
22、=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 8/19/202419离散数学求最优树的算法求最优树的算法( (Huffman算法算法) )给定实数给定实数w1,w2,wt，设，设w1w2wt。 连接权为连接权为w1, w2的两片树叶，得一个分支点的两片树叶，得一个分支点，其权为，其权为w1+w2。三、最优树 重复重复，直到形成，直到形成t- -1 1个分支点、个分支点、t片树叶为止。片树叶为止。 在在w1+w2, w3, , wt中选出两个最小的权，连接中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及它们对应的顶点（不一
23、定是树叶），得新分支点及所带的权。所带的权。8/19/202420离散数学9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 5627527697671395278/19/202421离散数学67139527952716671329000011110001101101118/19/202422离散数学例：求带权为例：求带权为1、1、2、3、4、5的最优树。的最优树。三、最优树WW( (T T) )=38=38=38=38 最优树不是唯一的，但是由最优树不是唯一的，但是由最优树不是唯一的，但是由最优树不是唯一的，但是由HuffmanHuffman算法得到的树算法得到的树算法得到
24、的树算法得到的树一定是最优树。一定是最优树。一定是最优树。一定是最优树。8/19/202423离散数学前缀前缀: :设设 = = 1 2 n-1 n是长度为是长度为n的符号串，称的符号串，称 其其子子串串 1, 1 2, 1 2 n-1分分别别为为 的的长长 度为度为1,2, ,n-1的的前缀前缀。 四、最佳前缀码四、最佳前缀码四、最佳前缀码四、最佳前缀码二元前缀码二元前缀码: :若若 i (i=1,2,m)中只出现中只出现0 0与与1 1两个符号，两个符号， 则称则称B为为二元前缀码二元前缀码。前缀码前缀码: :设设B= 1, 2, , m为一个符号串集合，若为一个符号串集合，若对对 于任意
25、的于任意的 i, j B，ij， i, j互不为前缀，则互不为前缀，则 称称B为为前缀码前缀码。8/19/202424离散数学四、最佳前缀码四、最佳前缀码四、最佳前缀码四、最佳前缀码(2)(2)如何产生二元前缀码？如何产生二元前缀码？定理定理: :任何一棵二元正则树对应一个二元前缀码。任何一棵二元正则树对应一个二元前缀码。定理定理: :任何一个二元前缀码对应一颗二元正则树。任何一个二元前缀码对应一颗二元正则树。0，10，110，11111，11，101，00101，01，001，00000，11，011，0100，0101例：判断下列符号串集合是否是前缀码。例：判断下列符号串集合是否是前缀码。
26、8/19/202425离散数学方法：方法：用用HuffmanHuffman算法产生最佳前缀码。算法产生最佳前缀码。例、例、在通信中，八进制数字出现的频率如下：在通信中，八进制数字出现的频率如下： 0 0：25%25%；1 1：20%20%；2 2：15%15%；3 3：10%10% 4 4：10%10%；5 5：10%10%；6 6：5%5%； 7 7：5%5% 求传输它们的最佳前缀码？求传输它们的最佳前缀码？ 求求传传输输1010n（n2 2）个个按按上上述述比比例例出出现现的的八八进进制制数数字字需要多少个二进制数字？需要多少个二进制数字？ 若用等长若用等长码码( (长为长为3) )传输需
27、要多少个二进制数字？传输需要多少个二进制数字？四、最佳前缀码四、最佳前缀码四、最佳前缀码四、最佳前缀码最佳前缀码：最佳前缀码：当要传输按着一定比例出现的符号串当要传输按着一定比例出现的符号串 时，需要寻找传输它们最省二进制数字时，需要寻找传输它们最省二进制数字 的前缀码，即最佳前缀码。的前缀码，即最佳前缀码。8/19/202426离散数学例：以例：以100100乘各频率为权，并按小到大排列，得乘各频率为权，并按小到大排列，得w1=5,w2=5, w3=10, w4=10, w5=10, w6=15, w7=20, w8=25。产生的最优树如下。产生的最优树如下。 0 01 (25%) 1 11
28、 (20%) 2 001 (15%) 3 100 (10%) 4 101 (10%) 50001 (10%) 6 00000 (5%) 7 00001 (5%)传传100100个按比例出现的八进制数字所需二进制数字个按比例出现的八进制数字所需二进制数字个数个数W( (T)=285)=285，所以传，所以传10n(n 2)个所用二进制数字个所用二进制数字应为应为2.85 10n。用等长码（长为用等长码（长为3 3）应该用）应该用3 10n个数字个数字, ,因此用最因此用最佳前缀码可节省传递数字。佳前缀码可节省传递数字。8/19/202427离散数学（1）由于在每一步选择两个最小的权的选法不唯一。
29、由于在每一步选择两个最小的权的选法不唯一。（2）因为两个权对应的顶点所放左右位置不同。因为两个权对应的顶点所放左右位置不同。（3）画出的最优树可能不同，最佳前缀码并不唯一，画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权相等，即它们都应该但有一点是共同的，就是它们的权相等，即它们都应该是最优树。是最优树。四、最佳前缀码四、最佳前缀码四、最佳前缀码四、最佳前缀码8/19/202428离散数学遍遍历历：对对一一棵棵根根树树的的每每个个顶顶点点访访问问且且仅仅访访问问一一次次称称为为遍遍历历一棵树一棵树。中序遍历法：中序遍历法：b a (f d g) c e五、树的遍历五、树
30、的遍历前前序序遍遍历历法法：a b (c (d f g) e)后后序序遍遍历历法法：b (f g d) e c) a 对对2 2元有序正则树的遍历方式：元有序正则树的遍历方式： 先序遍历法：访问次序为：树根、左子树、右子树先序遍历法：访问次序为：树根、左子树、右子树 后序遍历法：访问次序为：左子树、右子树、树根后序遍历法：访问次序为：左子树、右子树、树根 中序遍历法：访问次序为：左子树、树根、右子树中序遍历法：访问次序为：左子树、树根、右子树 8/19/202429离散数学用用2元有序正则树存放算式：元有序正则树存放算式： 最高层次的运算符放在树根上。最高层次的运算符放在树根上。 依次将运算符
31、放在根子树的根上。依次将运算符放在根子树的根上。 参加运算的数放在树叶上，参加运算的数放在树叶上，规定：被除数、被减数放在左子树树叶上。规定：被除数、被减数放在左子树树叶上。 五、树的遍历五、树的遍历8/19/202430离散数学例：例：用二叉有序正则树表示算式：用二叉有序正则树表示算式： (b+(c+d) a) (e f) (g+h) (i j) 五、树的遍历五、树的遍历8/19/202431离散数学波兰符号法波兰符号法: :按前序遍历法访问存放算式的二元有序按前序遍历法访问存放算式的二元有序正则树，其结果不加括号，规定每个运算符号与其正则树，其结果不加括号，规定每个运算符号与其后面紧邻两个数进行运算。后面紧邻两个数进行运算。前序遍历法的访问结果为前序遍历法的访问结果为: : b + c d a e f + g h i j 8/19/202432离散数学逆波兰符号法逆波兰符号法: :按后序行遍法访问，规定每个运算符与按后序行遍法访问，规定每个运算符与前面紧邻两数运算。前面紧邻两数运算。 后序行遍法的访问结果为后序行遍法的访问结果为: :b c d + + a e f g h + i j 小节结束小节结束8/19/202433离散数学
