图中参数与树型结构研究

来源 :华中师范大学 | 被引量 : 1次 | 上传用户:cocoxb
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
几十年来,图的支撑树特征问题一直是结构图论中一个重要的研究课题.该问题的产生和发展与结构图论中哈密尔顿问题的研究密切相关,因此受到国内外许多图论专家的关注.若图中存在一条哈密尔顿路,即说明图中存在恰好两个叶子的支撑树或是最大度等于2,即没有分支点的支撑树.自然就有如下问题:能否给出保证图中存在至多k个叶子的支撑树,或是图中存在有限个分支点的支撑树,或是图中存在最大度不超过k的支撑树等一系列问题的条件.同时,若图为哈密尔顿连通图,即说明图中存在以任意两点作为叶子集的支撑树,自然我们就可以试图探求在何种条件下,图中存在以任意k个点作为叶子集的支撑树,由此引出k-叶子连通图的判定问题.众所周知,判定一个图是否含一条哈密尔顿路从算法复杂性来讲是NP-完全的,从而对上述一系列有关保证图中是否存在具有相应特征的支撑树问题也是NP-完全的,于是对于这些问题的研究主要集中在给出相应的充分条件.目前在图中是否存在具有和哈密尔顿性相关的特征的支撑树问题的研究中主要从参数的角度进行刻画,运用坚韧度、独立数、连通度、领域并、度和等条件,集中讨论图中是否存在以下五类特征的支撑树的充分条件:1.图中存在最大度不超过k的支撑树;2.图中存在至多k个分支点的支撑树;3.给定连通度条件下,图中,特别地,K1,r-free图中存在至多k个叶子的支撑树;4.图中存在以任意k个点作为叶子集的支撑树;5.图中存在满足去掉所有叶子后,最大度至多为k的支撑树.本文主要研究了在满足一定连通度条件下,K1,4-free图和K1,5-free图中存在至多有限个叶子的支撑树的度和条件.首先考虑连通K1,4-free图,Kyaw证明了若图G是阶数为n的连通K1,4-free图,(i)若σ3(G)≥n,则G中含一条哈密尔顿路,即恰含两个叶子的支撑树;(ⅱ)当k≥3时,若σ’k+1(G)≥n一k/2,则G中存在至多k个叶子的支撑树.并且说明了结论中的界均为最好可能的.本文提高连通度,考虑m-连通K1,4-free图.证明了图G是阶数为n的m-连通K1,4-free图,其中m≥2,若O’m+3(G)≥n+2m-2,则G中存在至多3个叶子的支撑树.另一方面,本文也研究了连通K1,5-free图中类似的问题,证明了图G为连通K1,5-free图且阶数n≥77,若σ5(G)≥n-1,则G中存在至多4个叶子的支撑树.并且说明了该结论中度和的下界n-1是最好可能的.
其他文献
目的探讨维持性血液透析患者动静脉内瘘再次血栓形成的相关影响因素。方法选取因动静脉内瘘血栓形成而住院治疗的34例透析患者为病例组(A组),根据血栓形成次数将病例组分为初
板块构造学说是近代最盛行的全球大地构造理论。该学说的创立和进展,在全球构造理论方面打开了一扇通往未知世界的大门,使得迄今被视为不解之谜的地球活动大多得到了解释。
对基因编辑婴儿事件进行伦理评析,并结合目前文献中常见的反对胚胎基因编辑的伦理依据可知,一旦解决了胚胎基因编辑的安全性问题,完全禁止胚胎基因编辑的临床应用就不再具有
《史记》是一部百科全书式的史学著作,其中记载音乐方面的史料异常丰富,因此也可以说《史记》是一部具有音乐文化意义的史书。《史记》中除了两个音乐专篇《乐书》《律书》之
本试验通过对红地球一年生枝条中不同时期各个节位花芽中植物激素(脱落酸、生长素、玉米素核苷和赤霉素)、矿质元素(钙、铜、钾、镁、硼、锌和氮)、糖类(淀粉、可溶性糖和还
为对基于全国层面的土地发展权价值进行估算,并研究其土地发展权价值分布规律,运用理论模型分析法和空间计量经济分析法估算全国31个省份的土地发展权价值。通过研究,得出以