若干图类的子树或块割点子树计数算法研究

发布时间：2017-12-11 02:23

  本文关键词：若干图类的子树或块割点子树计数算法研究

  更多相关文章： 树 圈链图 子树 块割点子树 计数算法

【摘要】：图论和算法是计算机学科的主要研究领域,它们为解决众多科学问题提供理论依据和实施方案。子树数和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)的子树计数算法,并给出了两类链图关于子树数的极值、极值图及子树密度分析。
【学位授予单位】：大连海事大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O157.5

【参考文献】

中国期刊全文数据库 前4条

1 袁超;柴毅;;复杂网络的局部社团结构挖掘算法[J];自动化学报;2014年05期

2 朱莹;任立红;丁永生;Kongsuwan Kritaya;;背包问题DNA算法的反应设计及其生物实现(英文)[J];计算机学报;2008年12期

3 张莲珠 ,田丰;Extremal hexagonal chains concerning largest eigenvalue[J];Science in China,Ser.A;2001年09期

4 李晓明;网络可靠性综合的现状及其展望[J];计算机学报;1990年09期

中国博士学位论文全文数据库 前3条

1 张修梅;图的结构与图的子树个数[D];上海交通大学;2014年

2 王炳波;复杂网络拓扑结构度量指标及应用研究[D];西安电子科技大学;2014年

3 崔卫红;基于图论的面向对象的高分辨率影像分割方法研究[D];武汉大学;2010年

，

本文编号：1276818