资源描述：
《离散数学课件-第5章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1离散数学DiscreteMathematics汪荣贵教授合肥工业大学软件学院专用课件2011.062CHAPTER5Graphs5.1IntroductiontoGraphs图的概述5.2GraphTerminology图的术语5.3RepresentingGraphsandGraphIsomorphism图的表示和图的同构5.4Connectivity连通性5.5EulerandHamiltonPaths欧拉通路和哈密顿通路5.6PlanarGraphs平面图5.7Trees树1树的基本概念2几类常用树2-1判定树2-2有序二元
2、树2-3Huffman树3最小生成树§1树的基本概念在图论中：1、连通的无环图称为树。2、除根之外，度＝1的顶点称为叶子，度＞1的顶点称为分支点或者内点。叶子分支点根§1-1树的概念－13、多个树称为森林；4、孤立顶点叫做平凡树。123456789101512131114平凡树§1-1树的概念－25、若一棵树是图G的生成子图，则称该树为图G的生成树或支撑树；6、G－E(T)称为树T的余树，记作：T’；7、T’中的边称为图G的弦，也是树T的弦。1234567812345678余树弦§1-1树的概念－38、树——（1）不具明显层次的树(
3、a图)（2）具有层次的树(b图)a图12345678b图根互为兄弟互为父子1、若连通图G=(V,E)，n=
4、V
5、，则图的生成树有n－1条边。2、下面五个命题是等价的（1）G是一棵树；（2）G的任意两顶点间仅有一条道路；（3）G是连通的且m＝n－1；（4）G不包含回路且m＝n－1；（5）G不含回路而且在不相邻的两顶点间增加一条边，则有且仅有一条回路。证明略。树的基本性质§2几类常用树§2-1判定树(decisiontree)判定树是图论中最常见的模型之一，判定树把做出判决的逻辑关系用树的形式表现出来，使得条理清晰，一目了然。往往最后的
6、结果都集中在叶子顶点上。例2.1例2.1设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、d分别表示银币，a:b表示在天平上作比较。a:b＜＞＝a:cc重c轻＜＞＝a:dd重全真d轻＜＞＝a:ca轻b重＜＝a:cb轻a重＞＝例2.1－1容易看出，上例中方法并不唯一。a,b:c,d＜＞＝a:c＜＞＝d:cc轻a重＞＝a:c＝＜全真d:cb重d轻＜＞＝a轻c重＜＝a:b＝a:bb轻d重＜课后思考题已知有12个金币，其中有一个是假的，且不知道假币和金币的重量关系，现在要求用一个天平，
7、只称3次，把假币找出来。§2-2有序二元树1、定义1：图T是一棵树，把每边规定一个方向且使得任意的vi∈V(T),存在有向道路P(v0,vi),则称T是外向树，v0叫做根，把外向树之定向反过来，得到的有向树叫内向树。v0v0§2-1有序二元树－12、定义2：T为外向树，对任意的顶点v∈V(T)，都有d+(v)≤σ，则称T为σ元树；3、当e=(u,v)时，u称为v之父，v称为u之子；同父之子称为兄弟。4、除叶子外，每顶点皆有σ子时，称为典型σ元树；5、兄弟间有序时，叫有序树，有序树之序列叫做有序林。6、有序树当σ=2时，就叫有序二元树
8、。§2-1有序二元树－27、对有序二元树的顶点编码如下：(1)根不标码；(2)兄弟有序，作为兄，标0，右为弟，标1；(3)从根始到叶上的道路依次抄出各点之码，写在叶下方，称该叶的前缀；(4)全树的叶从左到有把它们的前缀依次抄出，叫做该树的前缀码，每个叶子的前缀后加逗号，最后一个叶子前缀后加句号。显然有序二元树与前缀码一一对应。§2-1有序二元树－3例如，0000，0001，001，010，011，100，101，11这一前缀码对应的有序二元树如下图所示：v001101010010101000000010010100111001011
9、1§2-1有序二元树－4取定一个有26个叶子的有序二元树，把它标出前缀码。再把每个叶子分别写上26字母，则可以用前缀码表示字母。例如，刚才的有序二元树的叶子写上字母如下：§2-1有序二元树－5如果收到一串数字：11，010，011，101，011，100，001，0000，0001，0000，100，001，0000，100。fv0011010100101010000000100101001110010111aghinxzZhixingafangan执行A方案§2-3Huffman树§2-3Huffman树－1定义：在v0为根，v1
10、,v2,…,vn为叶的有序二元树中，路径P(v0,vi)(i=1,2,…,n)的长度li叫做叶vi的码长。若pi(i=1,2,…,n)代表的事物出现的概率为pi，=1，使得m(T)＝＝min有序二元树T叫做带权p1,p2,…,pn的H
