论文部分内容阅读
“可图度序列问题”是图论中很有名而又较复杂的问题,国内外关于这个问题的结论很多,但涉及研究“可树度序列问题”以及“可超树度序列问题”却很少。而对于超图中的线性超树,由于它自身结构的特殊性,目前还没有得到对其悬挂边数目进行精确计算的有效算法以及关于特殊标号含圈广义线性超树计数方面的结论。鉴于此,本文分别在树、狭义超树、广义超树三部分中做了下列几个方面的工作。
首先,从分析树与其叶子总数之间的关系入手,通过引入分枝点并借助构造证明的思想,得到了判断可树度序列的充要条件和一系列推论,并且按照同样的方法把它推广到研究森林和树形图中。
其次,根据在研究超图的过程中常用到的推广延伸的思想,把图论中研究可树度序列的方法,通过分析超树与其孤立点总数之间的关系,推广应用到研究狭义超树和广义超树中。在其中主要利用超树的对应二部图作为研究的桥梁,来达到刻划线性超树的顶点与超边结构的目的,在非线性超树的研究中根据图论中边细分的思想,定义了超图对应二部图的点细分。最终,得到了判断可超树度序列的几个相关定理和一系列推论,并且通过探讨超图圈结构的不同定义,得到了关于狭义超树和广义超树之间关系的一些有意义的命题,从而进一步揭示了度序列与线性超树的关系。
然后,在超树中根据线性超树悬挂边与其孤立点之间的特殊对应关系,提出了求线性超树悬挂边数目的一种有效、可行的算法,其算法复杂度仅为 。在广义超树中根据线性超图和广义超树的性质,得出了一类标号含圈广义线性超树的计数上下界以及相应的多圈线性超图的计数上下界。
最后,通过举出商品销售问题和储藏点分布规划问题的具体事例,来说明本文所得部分关于树形图、超树的结论在整数规划模型中的应用,同时也加深了对广义超树的相关概念以及本文所得相关结论的理解。
本文所得结论,对于充实可图度序列理论,以及悬挂边、超图的计数理论与应用实践均是有益的。