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

摘要

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

目录

声明

摘要

第1章 绪论

1．1 研究背景和意义

1．2 子树和块割点子树(BC-子树)指标研究现状分析

1．2．1 子树指标

1．2．2 块割点子树(BC-子树)

1．3 研究内容

1．4 本文的组织结构

第2章 树的块割点子树(BC-子树)

2．1 符号和定义

2．2 一般树的块割点子树(BC-子树)

2．2．1 关于块割点子树(BC-子树)的极值树

2．2．2 树的“块割点子树核”(BC-子树核)

2．2．3 树的块割点子树(BC-子树)的计数

2．3 广义Bethe树的子树及块割点子树(BC-子树)

2．3．1 广义Bethe树、Bethe树及树枝状大分子图的子树数η(．)

2．3．2 广义Bethe树、Bethe树及树枝状大分子图的BC-子树数ηBC(．)

2．3．3 树枝状大分子图Tk，d的子树和BC-子树密度的渐进特性

2．4 本章小结

第3章 单圈图和无公共边的双圈图的块割点子树(BC-子树)

3．1 符号和定义

3．2 单圈图和无公共边的双圈图的OLDV-子树和ELDV-子树

3．2．1 单圈图的OLDV-子树和ELDV-子树

3．2．2 无公共边的双圈图的OLDV-子树和ELDV-子树

3．3 单圈图和无公共边的双圈图的块割点子树(BC-子树)

3．3．1 单圈图的块割点子树(BC-子树)

3．3．2 无公共边的双圈图的块割点子树(BC-子树)

3．4 单圈图和无公共边的双圈图的含指定顶点集的块割点子树(BC-子树)

3．4．1 含指定一个顶点的块割点子树(BC-子树)

3．4．2 含指定两个不同顶点的块割点子树(BC-子树)

3．5 本章小结

第4章 六元素环螺链图和聚苯六角链图的子树和块割点子树(BC-子树)

4．1 符号和定义

4．2 六元素环螺链图和聚苯六角链图的子树

4．2．1 六元素环螺链图的子树

4．2．2 聚苯六角链图的子树

4．2．3 六元素环螺链图和聚苯六角链图的子树数η(Gn)和η((-G)n)间的关系

4．2．4 六元素环螺链图和聚苯六角链图的子树密度

4．3 六元素环螺链图和聚苯六角链图的块割点子树(BC-子树)

4．3．1 六元素环螺链图的块割点子树(BC-子树)

4．3．2 聚苯六角链图的块割点子树(BC-子树)

4．3．3 六元素环螺链图和聚苯六角链图的块割点子树密度

4．3．4 六元素环螺链图和聚苯六角链图的块割点子树数间的关系

4．4 本章小结

第5章 六角形链图和亚苯基链图的子树

5．1 符号及定义

5．2 六角形链图和亚苯基链图的子树数

5．2．1 六角形链图的子树

5．2．2 关于子树数的极值六角形链图

5．2．3 亚苯基链图的子树

5．3 例子及基于树收缩(TCB)的子树计数算法

5．4 六角形链图和亚苯基链图的子树密度

5．5 本章小结

第6章 结论与展望

6．1 结论

6．2 展望

参考文献

附录

攻读学位期间的研究成果

致谢

作者简介