离散数学第8章+图论8树

《离散数学第8章+图论8树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章图论-28.1Euler图与Hamilton图8.2树8.2.1树的概念和基本性质8.2.2几类常用树根树有序树最优二叉树8.2.3生成树8.3平面图8.2树树的术语起源于植物学和家谱学。早在1857年，英国数学ArthurCayley(1821—1895)就发现了树，当时他正在试图列举形为CnH2n+2的化合物的同分异构体。树具有广泛的应用，特别在计算机科学与管理科学中。如用树构造存储和传输数据的有效编码，用树构造最便宜的电话线连接分布式计算机网络，用树模拟一系列决策完成的过程等。8.2.1树的概念和基本性质在图论中：1、连通的无环图称为树。2、除根之外，度＝1的顶

2、点称为叶子，度＞1的顶点称为分支点或者内点。叶子分支点根8.2.1树的概念和基本性质3、多个树称为森林；4、孤立顶点叫做平凡树。123456789101512131114平凡树8.2.1树的概念和基本性质[定理]T=(V,E)是结点数n=

3、V

4、1的树，则下述命题等价：（1）T是无回路的连通图；（2）T是连通的，且有n1条边；（3）T有n1条边，且T中无回路；（4）T的任意两点间有且只有唯一的通路；（5）T中无回路，但若在T的任一对不相邻的顶点之间增加一条边，则构成T中的唯一回路。根树8.2.2几类常用树[有向树]一个弱连通有向图，若去掉方向后得到一棵树，则称此有向图为

5、一棵有向树，记为T。[根树]一棵有向树T，若其中有且仅有一个结点v0的入度为0，其余结点的入度为1，则称T是一棵以v0为根的根树或外向树。其中出度为0的结点称为有根树的叶子。把外向树之定向反过来，得到的有向树叫内向树。v0v08.2.2几类常用树根树通常画成倒长的；一个结点的子结点画在它的下一层，边的方向省略；“同辈兄弟”画在同一层。8.2.2几类常用树[树的高度]设有根树T=(V,A)，v0为树根。uV的深度是从v0开始到达u的有向路的长度，T的高度是从v0到T的叶子的最长路的长度。根结点深度为0，称为第0层；深度同为i的结点构成树的第i层；具有最大深度的结点的深度称为

6、树的深度（高度）。8.2.2几类常用树TreeNodeLevelandPathLength8.2.2几类常用树有序树[定义]对有向树T=(V,A)，若u,vV且A，则称u为v的父亲，v为u的儿子。若从u到v存在有向道路，则称u是v的祖先，v是u的后代（子孙）[有序树]将各树的每个结点的所有儿子按次序排列，称这样的根树为有序树。有序树的每个结点的出度小于或等于m时，称为m叉有序树。有序树的每个结点的出度只为0或m时，称为m叉正则有序树。8.2.2几类常用树例设有4个银币，已知其中3个一定是真的，真假的区别在于银币的重量，现用一天平设法找出假币。解：用a、b、c、

7、d分别表示银币，a:b表示在天平上作比较。a:b＜＞＝a:cc重c轻＜＞＝a:dd重全真d轻＜＞＝a:ca轻b重＜＝a:cb轻a重＞＝8.2.2几类常用树容易看出，上例中方法并不唯一。a,b:c,d＜＞＝a:c＜＞＝d:cc轻a重＞＝a:c＝＜全真d:cb重d轻＜＞＝a轻c重＜＝a:b＝a:bb轻d重＜8.2.2几类常用树三、最优二叉树[二叉树]除树叶外，每个结点的最多有两个子结点，分别称为左子结点和右子结点的根树称为二叉树二叉树的另外一个定义：二叉树或者是空树，或者有一个根结点和两个分别称为左右子树的二叉树构成。[二叉树的性质]第i层的结点数最多为2i；深度为k的二叉树最

8、多有2k+1-1个结点；记二叉树出度为2的结点数目为n2，叶子数目为n0，则有：n0=n2+1多元树与二叉树的对应关系：以结点的最左儿子为对应二叉树中该结点的左儿子；以结点的右兄弟为对应二叉树中该结点的右儿子。8.2.2几类常用树[满二叉树]二叉树的每个结点的出度或者是0或者是2。满二叉树也称正则二叉树[完美二叉树]满二叉树且所有结点在同一层。对完美二叉树的结点按从上到下，同层结点从左到右的原则编号，得到结点从1~2k+1-1的编号序列。得到上述结点编号的二叉树称为编号二叉树。[完全二叉树]若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h

9、层从右向左连续缺若干结点，这就是完全二叉树。。8.2.2几类常用树高度为k的完全二叉树，其k-1层以上结点构成一棵高度为k-1的完美二叉树。完全二叉树的叶结点或者在同一层或者在相邻的两层。1671213141511109584231211109876543211671415958423满二叉树完美二叉树完全二叉树8.2.2几类常用树三、最优二叉树[定义]设T是有t片叶子的二叉树，其中t片叶子分别带有非负实权，则称T为加权二叉树。称W(T)＝为二叉树T的权，其中hi为带权wi的树叶vi的层数。在所有的带权的二叉树中，