论文部分内容阅读
图论和算法是计算机学科的主要研究领域,它们为解决众多科学问题提供理论依据和实施方案。子树数和BC-子树数是两个重要的图结构化拓扑参数,跟混合网络局部可靠性及化合物的物理和化学性质关系密切。本文基于图论,通过Tutte和新的三元Tutte多项式和结构分析的方法,研究树、单圈图、无公共边的双圈图、以及与PM2.5中重要的致癌物质分子对应的六元素环螺链图、聚苯六角链图、六角形链图和聚亚苯基链图的子树或BC-子树计数算法问题,取得如下研究成果：(1)给出了新的三元Tutte多项式,并通过树“收缩”操作,给出了树的含给定顶点且所有叶子到该顶点的距离都是奇(偶)数的子树的计数算法,并进一步给出了树的所有、含任给一个、两个顶点的BC-子树的计数算法,确定了n个顶点树中具有最大和最小BC-子树数的树分别为星树和路径,给出了广义Bethe树的子树及BC-子树数,提出BC-子树密度的概念并分析了树枝状分子图的BC-子树密度渐进特性。(2)基于新的三元Tutte多项式和树的BC-子树的计数算法,针对单圈图和无公共边双圈图,给出了含给定顶点且所有叶子到该顶点的距离都是奇(偶)数的子树的计数算法,在此基础上,给出了计算单圈和无公共边的双圈图的全部、含任意一个、两个顶点的BC-子树的生成函数的计数算法,并给出相应算法实现的实例分析。(3)针对六元素环螺链图G。和聚苯六角链图(?),通过Tutte和新的三元Tutte多项式、圈权重的“收缩传递”及结构分析的方法,首先给出Gn(Gn)的含割点C仡(尾点tn)的子树及含cn(tn)且所有的叶子到cn(tn)的距离分别是奇数和偶数的子树的生成函数,然后推导出它们的子树和BC-子树的生成函数,给出了它们关于子树(BC-)子树数间的关系、极值、极图结构,首次将Wiener和子树数指标的“反序”关系证明推广到分子链图上,并分析了这两类链图的子树和BC-子树密度。(4)针对六角形链图Gn、聚亚苯基链图瓦,通过Tutte多项式和结构分析的方法,首先给出Gn(Gn)以及辅助图(?)-1)的含相邻六元素圈的公共边(un,vn)(相邻四和六元素圈的公共边(un,vn)及(pn-1,qn-1))的子树的生成函数,然后推导出它们子树的生成函数,在此基础上给出两类链图的基于树收缩(TCB)的子树计数算法,并给出了两类链图关于子树数的极值、极值图及子树密度分析。