对树的Wiener Index逆问题的研究

论文摘要

组合化学是近十几年逐渐发展并成熟起来的一门学科,它将化学合成、组合理论、计算机辅助设计融于一体,在短时间内将不同构建模块经过连接形成化合物库,再对库成分进行筛选优化,得到可能的有目标功能的化合物结构。通过计算机辅助设计可以极大提高库的组成并同时控制库的大小,因而计算机技术正在组合化学中发挥着越来越大的作用。 经过长期的研究,科学家们发现很多化合物的物理性质和化学性质与它们的拓扑性质密切相关。Wiener Index就是一个与化合物的物理化学性质密切相关的拓扑系数,它的性质已经被广泛应用于组合化学领域中。树的Wiener Index逆问题是组合化学中的一个重要问题,Goldman于2000年提出的动态规划算法虽然理论上可以解决此问题,但是算法的计算量很大,程序复杂性和运行速度方面也不太理想。 本文首先对树的Wiener Index和其它一些拓扑系数的关系进行了分析,并进一步利用这种关系对原算法进行了改进,极大地减小了原算法的搜索空间和递归次数;在此算法基础上本文又对树的Wiener Index判定逆问题的算法做出了改进,使其在计算量、程序复杂性和运行速度方面明显优于已有算法;最后本文给出了一种新的解决树的WienerIndex构造逆问题的算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 组合化学的发展历史
• 1.1.1 组合化学的创立与发展
• 1.1.2 组合化学的研究方法
• 1.1.3 组合化学对相关学科的影响
• 1.2 组合化学中的重要系数简介
• 1.2.1 Wiener Index
• 1.2.2 σ-Index
• 1.2.3 c-Index
• 1.3 组合化学中的逆问题
• 第二章 树的Wiener Index逆问题算法的提出
• 2.1 基本定义和定理
• 2.2 树的Wiener Index逆问题
• 2.3 Wiener Index的递归联系
• 2.4 Wiener Index逆问题算法的提出
• 第三章 对树的Wiener Index逆问题算法的改进
• 3.1 原算法的弊端及初步的改进
• 3.2 对算法的进一步研究和改进
• 3.3 改进后算法与原算法运行效率的比较
• 3.4 Wiener Index构造逆问题算法的改进
• 第四章 总结与展望
• 参考文献
• 致谢
• 硕士研究生期间发表的论文
• 硕士研究生期间参与的工作
• 学位论文评阅及答辩情况表