王 宇，刘燕丽，2*，陈劭武

（1.武汉科技大学理学院，武汉 430081；2.冶金工业过程系统科学湖北省重点实验室（武汉科技大学），武汉 430081）

（∗通信作者电子邮箱yanlil2008@163.com）

0 引言

图被广泛应用于描述事物的结构或事物之间的复杂关系，如互联网、社交网络、蛋白质交互网络、化学分子结构、电力网、公路网、图像处理中的属性图等［1］。给定模式图和目标图，子图同构问题是判断在目标图中是否存在与模式图完全同构的子图。最大公共子图（Maximum Common induced Subgraph，MCS）问题是子图同构问题的优化形式，即在模式图和目标图中找到满足同构条件的最大子图。

图匹配问题广泛应用于图像处理［2-3］、生物化学［4］、信息检索［5］、模式识别［6］、社交网络［7］等领域。图匹配问题可以识别数据集成中元数据或模型的对应关系。在生物学和生物化学领域，基因序列中每个基因可以表示为图的顶点，若染色体上两个基因相邻，则图中对应的顶点之间存在边。利用图匹配可以发现基因组中是否含有相同的基因。在模式识别中，图匹配可以提取多个图像中相似的对象。在Facebook等社交网络中，顶点表示每个用户，有向边表示用户之间的好友关系。利用已有的社交关系，为用户推荐好友，也是图匹配问题的应用之一。

文献［8］提出了基于约束规划（Constraint Programming，CP）模型的树搜索算法。对于给定的模式图P和目标图T，每次选择一个〈v，w〉（v∈VP，w∈VT）顶点匹配对作为空间搜索树的分支点；界函数计算子树含有的顶点的最大待匹配对个数，作为剪枝操作的上界。提高CP 类算法效率的关键工作是分支顺序和定界函数的设计。……