度序列与树、超树

来源 :重庆大学 | 被引量 : 0次 | 上传用户:txl8909
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
“可图度序列问题”是图论中很有名而又较复杂的问题,国内外关于这个问题的结论很多,但涉及研究“可树度序列问题”以及“可超树度序列问题”却很少。而对于超图中的线性超树,由于它自身结构的特殊性,目前还没有得到对其悬挂边数目进行精确计算的有效算法以及关于特殊标号含圈广义线性超树计数方面的结论。鉴于此,本文分别在树、狭义超树、广义超树三部分中做了下列几个方面的工作。 首先,从分析树与其叶子总数之间的关系入手,通过引入分枝点并借助构造证明的思想,得到了判断可树度序列的充要条件和一系列推论,并且按照同样的方法把它推广到研究森林和树形图中。 其次,根据在研究超图的过程中常用到的推广延伸的思想,把图论中研究可树度序列的方法,通过分析超树与其孤立点总数之间的关系,推广应用到研究狭义超树和广义超树中。在其中主要利用超树的对应二部图作为研究的桥梁,来达到刻划线性超树的顶点与超边结构的目的,在非线性超树的研究中根据图论中边细分的思想,定义了超图对应二部图的点细分。最终,得到了判断可超树度序列的几个相关定理和一系列推论,并且通过探讨超图圈结构的不同定义,得到了关于狭义超树和广义超树之间关系的一些有意义的命题,从而进一步揭示了度序列与线性超树的关系。 然后,在超树中根据线性超树悬挂边与其孤立点之间的特殊对应关系,提出了求线性超树悬挂边数目的一种有效、可行的算法,其算法复杂度仅为 。在广义超树中根据线性超图和广义超树的性质,得出了一类标号含圈广义线性超树的计数上下界以及相应的多圈线性超图的计数上下界。 最后,通过举出商品销售问题和储藏点分布规划问题的具体事例,来说明本文所得部分关于树形图、超树的结论在整数规划模型中的应用,同时也加深了对广义超树的相关概念以及本文所得相关结论的理解。 本文所得结论,对于充实可图度序列理论,以及悬挂边、超图的计数理论与应用实践均是有益的。
其他文献
继承系统是建立在知识分层结构上的知识描述体系, 分层结构的第一个优点就是它是一个有效的推理方式,另一个优点就是经过简洁的描述,它能够更有效的进行搜索。继承系统最初的目
1952年Markowitz开创性地提出了证券组合选择问题的均值-方差模型,这一模型奠定了现代投资组合理论的基础,他也因此获得了1990年的诺贝尔经济学奖.经典的均值-方差模型最初是假
本文给出了矢丛上Sasaki度量的局部表示,特别得到单位切丛~r1S2n+1上Sasaki度量的表达式.在此度量下计算了奇数维球面S2~+l上Hopf向量场VH的体积,由Gysin序列得到了T1S2n+1的上
本文的主要目的是使用局部化的思想对动力系统熵的理论(包括序列熵和复杂性函数)进行深入的研究,既有对原有的点对和点串理论的细化,也发展了新的局部化方法,并寻求其在动力系统