树密度和平均顶点数.doc

万方数据 Submitted iN total ful?lmeNt of the requiremeNts for the degree of Master iN Mathematics The DeNsity aNd Average Number of Nodes iN a Tree J???? T? Supervisor Prof. X??????? Z???? D????? ?? M??????????, S????? ?? S??????? J??? T??? U????????? S??????? J??? T??? U????????? S???????, P.R.C???? JaNuary, 2013 万方数据 万方数据 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研 究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本 人承担。 学位论文作者签名：  日 期：  年  月  日  万方数据 万方数据 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。  保 密 ?，在 本学位论文属于 不必威体育官网网址 ?。 （请在以上方框内打“√”） 学位论文作者签名：  年解密后适用本授权书。 指导教师签名：  日 期：  年  月  日  日 期：  年  月  日  万方数据 万方数据 万方数据 万方数据 万方数据 上海交通大学硕士学位论文 树的密度与平均顶点数  摘要  摘  要  　本文研究了阶数为 N 的树，在不同直径下对应的 k 阶子树个数，以及该 树的子树的平均节点数和密度。此外，文章还讨论了阶数和直径固定条件下， 平均节点数和密度受节点分布的影响情况，求出了他们对应的极值并加以证 明。  关键词： 子树  平均节点数  密度  — i — 万方数据 万方数据 上海交通大学硕士学位论文  ABSTRACT  The DeNsity aNd Average Number of Nodes iN a Tree ABSTRACT IN this paper,the Number of k-subtree,the average Number of Nodes iN a subtree aNd its deNsity for a giveN tree with N Nodes uNder di?erreNt diametres are discussed. IN additioN, the paper also shows that the meaN aNd deNsity of T are impacted by the Nodes distributioN while the order Number aNd diameter are uNder ?xed coNdi- tioNs.Furthermore, we also obtaiN their correspoNdiNg extreme aNd give the proof. KEY WORDS: subtree,average of Nodes, desity — iii — 万方数据 万方数据 上海交通大学硕士学位论文 摘要 ABSTRACT 目录 第一章 绪论  目  录  目录 i iii v 1  1.1 1.2 1.3 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 基本概念介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 课题的研究现状与工作内容 . . . . . . . . . . . . . . . . . . . . .  1 2 4  第二章 较小直径下树的研究  7  2.1 直径为 2 的树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  7 2.1.1 2.1.2 全局平均 . . . . . . . . . . . . . . . .