论文摘要
子图同构是图论中一个重要问题,对这个问题的研究不仅具有计算复杂度理论上的价值,同时也有着广泛应用,尤其在生物信息学和模式识别等领域中,很多基础的问题其实都可以转化成子图同构来加以解决。传统的子图同构是给定两个图,判断其中一个图是否是另外一个的子图。子图同构用在图数据库上,就是我们最常见的搜索操作,用户输入一个子结构,系统返回数据库中所有包含该子结构的图。如果我们进一步增强搜索操作的功能,允许用户不仅可以定义一个普通的子图,还可以给图中每条边定义一个正整数值得权重,这个权重表示这条边两个顶点之间必须要满足的距离上限,数据库中的任何一个图,两两相对应的顶点只要满足这些用户定义的距离上限,我们就认为它们是同构的。显然这样的设定可以增加数据库搜索功能的灵活性,给用户带来更大的方便。我们把带权重的子图同构问题称为扩展的子图匹配。扩展的子图匹配中,怎么样有效的处理权重信息是问题的关键。在这篇文章中,我们对扩展的子图匹配问题提出了新的方法,运用了Ullmann剪枝和QuickSl的不同特性,提出了优化处理距离信息的加边算法。前一种根据Query中各个顶点到不同标签的顶点的最短距离来进行剪枝,后一种采用动态的加边算法,来减少加边的运算时间,适合于处理规模不大的稀疏图,例如用图表示的化学分子结构等。文章最后给出了在AIDS数据库上的实验结果和分析,测试了在不同距离值的条件下,算法的性能对比。