离散数学课件资料PPT学习教案

1、会计学1离散数学课件资料离散数学课件资料2021-10-172第1页/共32页2021-10-173树的等价定义定理第2页/共32页2021-10-174例：例：画出画出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)11，(T)55。故。故T T的度数列必为以下情况之一：的度数列必为以下情况之一：第3

2、页/共32页2021-10-175第4页/共32页2021-10-176：第5页/共32页2021-10-177第6页/共32页2021-10-178推论推论1:推论推论2 : 定理第7页/共32页2021-10-179第8页/共32页2021-10-1710meee ,21maaa ,21maaa 21 i非环，若是环，则放弃非环，若是环，则放弃第9页/共32页2021-10-1711abcdegf195141827168213ae12dcbgf7148531621: :7121819第10页/共32页2021-10-1712第11页/共32页2021-10-1713第12页/共32页202

3、1-10-1714第13页/共32页2021-10-1715分类分类：根据根树根据根树T中每个分支点儿子数以及是否有序：中每个分支点儿子数以及是否有序：第14页/共32页2021-10-1716第15页/共32页2021-10-1717 tiiiWLWtW1)()(第16页/共32页2021-10-1718W(T1)=22+22+33+53+32=38W(T2)=34+54+33+22+21=47W(T3)=33+33+52+22+22=36 第17页/共32页2021-10-1719 重复，直到形成重复，直到形成t- -1 1个分支点、个分支点、t片树叶为止。片树叶为止。 在在w1+w2,

4、w3, , wt中选出两个最小的权，连接中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及它们对应的顶点（不一定是树叶），得新分支点及所带的权。所带的权。第18页/共32页2021-10-17209例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 562752769767139527第19页/共32页2021-10-17216713952795271667132900001111000110110111第20页/共32页2021-10-1722第21页/共32页2021-10-1723二元前缀码二元前缀码: :若若 i (i=1,2,m)中只出现中只出现0

5、0与与1 1两个符号两个符号， 则称则称B为为二元前缀码二元前缀码。前缀码前缀码: :设设B= 1, 2, , m为一个符号串集合，若对为一个符号串集合，若对 于任意的于任意的 i, j B，i j， i, j互不为前缀，则互不为前缀，则 称称B为为前缀码前缀码。第22页/共32页2021-10-1724(2)(2)如何产生二元前缀码？如何产生二元前缀码？定理定理: :任何一棵二元正则树对应一个二元前缀码。任何一棵二元正则树对应一个二元前缀码。定理定理: :任何一个二元前缀码对应一颗二元正则树。任何一个二元前缀码对应一颗二元正则树。0，10，110，11111，11，101，00101，01，

6、001，00000，11，011，0100，0101例：判断下列符号串集合是否是前缀码。例：判断下列符号串集合是否是前缀码。第23页/共32页2021-10-1725四、最佳前缀码四、最佳前缀码最佳前缀码：最佳前缀码：当要传输按着一定比例出现的符号串当要传输按着一定比例出现的符号串 时，需要寻找传输它们最省二进制数字时，需要寻找传输它们最省二进制数字 的前缀码，即最佳前缀码。的前缀码，即最佳前缀码。第24页/共32页2021-10-1726 0 01 (25%) 1 11 (20%) 2 001 (15%) 3 100 (10%) 4 101 (10%) 5 0 0 0 1 (10%) 6 0

7、 0 0 0 0 (5%) 7 0 0 0 0 1 (5%)传传100100个按比例出现的八进制数字所需二进制数字个按比例出现的八进制数字所需二进制数字个数个数W( (T)=285)=285，所以传，所以传10n(n 2)个所用二进制数字个所用二进制数字应为应为2.85 10n。用等长码（长为用等长码（长为3 3）应该用）应该用3 10n个数字个数字, ,因此用最因此用最佳前缀码可节省传递数字。佳前缀码可节省传递数字。第25页/共32页2021-10-1727（1）由于在每一步选择两个最小的权的选法不唯一。由于在每一步选择两个最小的权的选法不唯一。（2）因为两个权对应的顶点所放左右位置不同。因

8、为两个权对应的顶点所放左右位置不同。（3）画出的最优树可能不同，最佳前缀码并不唯一，画出的最优树可能不同，最佳前缀码并不唯一，但有一点是共同的，就是它们的权相等，即它们都应但有一点是共同的，就是它们的权相等，即它们都应该是最优树。该是最优树。四、最佳前缀码四、最佳前缀码第26页/共32页2021-10-1728中序遍历法：中序遍历法：b a (f d g) c e前序遍历法：前序遍历法：a b (c (d f g) e)后序遍历法：后序遍历法：b (f g d) e c) a 对对2 2元有序正则树的遍历方式：元有序正则树的遍历方式： 先序遍历法：访问次序为：树根、左子树、右子树先序遍历法：访问次序为：树根、左子树、右子树 后序遍历法：访问次序为：左子树、右子树、树根后序遍历法：访问次序为：左子树、右子树、树根 中序遍历法：访问次序为：左子树、树根、右子树中序遍历法：访问次序为：左子树、树根、右子树 第27页/共32页2021-10-1729第28页/共32页2021-10-1730第29页/共32页2021-10-1731前序遍历