论文摘要
组合化学是一门应用在药物分子设计和分子识别中的新兴的重要的技术。它是一种实验室的方法，目的是通过“大规模并行”筛选化合物库以发现具有某种生物活性的化合物。这种方法的应用主要是基于实验设计和计算数学模型的交互。药物和其它化合物可以用多边形模型表示，其中各顶点表示分子的一个原子，而原子间的共价联系则用边表示。这种由化合物的分子得到的多边形我们称为分子图，这个多边形可以是一条路、一棵树或者一个普通的图。定义在这个图上的指标—Wiener索引，是一个与化合物的物理化学性质密切相关的拓扑系数。前面对Wiener索引已经作了大量的工作，以前对Wiener索引的研究主要分为两种类型：图的Wiener索引问题以及Wiener索引逆问题。Wiener索引逆问题指：给定一个整数n，是否存在一棵树T，使得W（T）=n，以及如何计算更有效率。Wiener索引猜想指：除了有限的集合外，所有的正整数都是某一棵树的Wiener索引值。这个猜想至今没有得到证明，但是研究该问题的理论不断得到简化。2000年，Goldman et al借助于索引值之间的递归联系，提出了一个从较小的子树构造树的动态规划算法。该算法虽然可以在理论上解决此问题，但是算法的计算量很大，程序复杂性和运行速度也不太理想。本文首先对树的Wiener索引和其它一些拓扑索引的关系进行了分析，并进一步利用这种关系对原算法进行了改进，极大地减小了原算法的搜索空间和递归次数。然后，又对上述猜想作了进一步的研究：通过设计更有效的算法来证明上述猜想。以前的研究都侧重于通过枚举所有可能的树来证明该猜想，本文通过设计一种新的数据类型—树族，在这种数据类型中来证明上述猜想就已足够。本文围绕树的Wiener索引逆问题展开深入的研究，主要成果如下：1)对Goldman提出的算法进行了改进，通过比较得出，改进后的算法在搜索空间和递归次数方面都明显优于原算法，并且给出了新算法和原算法在递归调用次数上的实验对比结果；2)提出了一种新的数据结构—树族，比较系统的分析了这种树族的结构和性质，因此显示在证明Wiener索引猜想问题的时候不必搜索指数级个数的所有可能的树；3)提出了几种有效的解决树的Wiener索引逆问题的算法。利用Frederickson与Johnsons的矩阵搜索算法，可以将该算法的时间复杂度降到O(n3／2)，并且利用该算法可以验证到108以下的数，而Goldman提出的算法最大只能验证到104。