生成树中的若干极值问题

来源 :福州大学 | 被引量 : 0次 | 上传用户:caoerduo
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
判定一个给定图是否含Hamilton路的问题是著名的NP一完全问题。一个图的生成树是包含了它所有顶点的树。一条Hamilton路可以看做一棵只含两片叶子的特殊生成树。对于一个给定的图,它是否含有一棵满足特殊性质的生成树?这个问题是对Hamilton路问题的推广,而且现在普遍认为不可能找到这个问题的非平凡的充要条件。蜘蛛是一种最多有一个顶点的度大于等于3的树,彗星是一种最多有一条腿的长度大于等于2的蜘蛛。这篇论文主要给出了两个关于给定图包含一颗生成彗星的度条件,回答了Flandrin等人提出的一个的问题。在第一章,我们首先介绍了这篇论文里所要用到的有关生成树的符号和术语,接着我们介绍生成树中一些的重要的定理和问题,这些结果都与Hamilton路的问题到生成树的推广有关,多数结论从生成树的性质出发,其中包括了:生成树中所含叶子尽可能少,生成树中的最大点度尽可能小,生成树的分支顶点数尽可能少,以及其它一些性质。在第二章我们用反证法和分类讨论的办法证明一个生成彗星存在性的度和条件,并且给出例子说明这个条件是紧的。在第三章我们证明另外一个生成彗星存在性的度和条件,与第二章中使用的方法类似,并给出例子说明这个条件对于顶点数较小时也是紧的。当图的顶点数足够大的时候,这个度和条件不太可能是紧的,所以最后我们提出了一个猜想,这个猜想如果成立的话,那么猜想中提出的度和条件是紧的。
其他文献
纤维增强树脂基复合材料具有比模量、比强度高,制备工艺简单和易加工等优点,在航空航天、汽车工业和建筑等领域得到广泛应用。但是,复合材料由于抗冲击韧性相对较差,在遭受平
1925年,R.Nevanlinna建立了亚纯函数的两个基本定理,开始了值分布理论的近代研究。几十年来,亚纯函数的值分布理论的新发展都是Nevanlinna理论为基础的。在此基础上,本文讨论
图可以作为构造大量数学模型的有利工具.对图论的研究已经有两百多年的历史,其中图染色理论在图论研究中占有重要的地位,图的染色理论在最优化,计算机理论,网络设计,Hessians
Hilbert空间中的框架概念是由Duffin和Schaeffer在1952年研究非调和Fourier级数时正式提出的,近年来,框架理论的研究已经取得了一系列的研究成果。随着对框架理论研究的迅速发
图谱理论作为一门独立的学科有其独特研究方式、方法。图谱理论中常用的几种研究方法有代数方法、矩阵论方法、图运算法等。树是比较简单而特殊的一类图,对于树的最大谱半径的
本文主要研究了利用价值函数求解变分不等式问题的算法.主要研究内容如下:第二章利用价值函数将变分不等式问题等价转化成一个约束最优化问题,结合新的大步长非单调线搜索技术
目的采用准靶向代谢组学技术,检测肾阴虚DOR患者卵泡液代谢组学的改变;以“以药测证”的方法分析比较补肾中药干预前后肾阴虚证候积分的变化以及卵泡液代谢物变化,以期探寻肾阴虚不孕中医证候的潜在标志物。方法使用前瞻随机对照的方法,选取本中心行IVF-ET/ICSI-ET辨证为肾阴虚的患者57例,按照随机数字表法随机分成两组,实验组28例,取卵周期服用六味地黄丸至HCG日,用药当天以及HCG日填写肾阴虚证
本毕业论文主要研究了非赋权图中过指定顶点长圈的存在性问题。在第一章中,我们介绍了图论长圈领域的基本概念和术语,我们所研究问题提出的背景和已知的结果,以及我们所得到
分数阶微分方程边值问题有着广泛的实际来源和理论应用,正解更有着重要的实际意义.本文主要研究一类具体的常微分方程边值问题正解的存在性,全文由五章组成.第一章,绪论部分介
如果一个连通图的任意两个圈至多有一个公共点,则称它是一个仙人掌图。令是一个n点连通图G的拉普拉斯矩阵的特征多项式。熟知,如果G是一个树,则cn-2和cn-3分别是G的维纳指标