论文部分内容阅读
图论中,决定图的不变量的取值范围和极值图是一个非常重要并且活跃的研究课题.一般来说,对于多种图类(特别是树类),关于子树个数的极大(小)值的图恰好对应一些化学指数(如 Wiener指数)的极小(大)值的图或者是类似结构的图.然而研究表明,这种关系不是对所有的图类都保持,因此确定关于子树数的极值图是不容易的.近年来,虽然关于图的子树数研究很活跃并且有一些好的结果,但是到目前为止,还是有一些问题没能完全解决.本文主要围绕给定度序列树集关于子树数的极值图的结构分析和算法进行研究. 首先,我们采用了两种不同的方法讨论给定度序列树集中关于子树数的极大值问题.一方面,利用结构分析方法研究了树关于子树数的一些性质.这些结果能够用来刻画出含子树最多的图结构,即是贪婪树.此结果推广了Kirk和Wang的结果;给定两个不同的度序列π和π1,如果π△π1,则贪婪树T*π中所含的子树数一定比Tπ1中所含的子树个数;作为以上结论的应用,我们推导出在[60],[46]中的结果,正好跟分别由Wang和Zhang等证明得到的关于Wiener指数最小的树结构一致.另外我们利用优超的结论,确定了顶点数为n且独立数为α的树集以及匹配数为β的树集中含子树数最多的树结构以及子树数.另一方面,我们利用算法,对于给定任意一个树,保持度序列不变的情况下,明确地刻画了如何获得子树数最多树结构的过程并且确定了子树数极大的树结构.这些结果引出一些有趣的问题并能够洞察出第二大子树数结构特性. 其次,很自然地我们对含有最少子树的树图结构的性质进行研究,即一定是毛毛虫树;进一步对给定度序列的毛毛虫树集进行分析,得到毛毛虫树集关于子树数最大和最小图结构性质;通过以上结果,我们确定了给定最大度的树集含子树最少的树结构;通过对含叶较多的树集的极小图的确定,发现很难最终确定极小图结构.