图作为一种数据结构能够简洁有力地刻画出普遍事物间的联系,因此基于图的数据挖掘与管理技术无论在学术研究还是工业应用上都享有重要的地位。这其中最基本的任务是如何在图数据集中找到给定的查询图,也就是子图匹配问题。对于正在蓬勃发展的图数据库,生物信息学和社会网络分析等领域而言,一个高效的子图匹配算法的重要性不言而喻。子图匹配的数学基础是图论中的经典问题子图同构,一个著名的NP问题。可想而知,设计高效的子图匹配算法面临着相当巨大大的挑战。目前,子图匹配算法的研究工作主要有两个问题。其一是针对一张边数较多的图如何进行有效的过滤,其二是如何选择顶点搜索顺序来加快子图同构搜索的速度。特别是后者是近年来子图匹配研究的焦点。针对上述情况,本文提出了一个多段图模型(MGSM)用于指导顶点搜索顺序的选择。根据这个模型得到优化搜索顺序的两个关键点：特征选择和代价(导出子图)估计。其中,第一个关键点与过滤技术紧密相关,以此出发可以对以往算法的过滤技术进行改进。针对第二个关键点,本文提出了一种称为伪树估计的的代价估计方法。基于上述工作,本文设计了一个精确子图匹配算法Tps(Three-Phase-Searching)。实验结果表明：Tps算法不仅具有显著的高效性,同时优化的顶点搜索顺序对图过滤过程和验证过程同样有效。另外,本文在对精确与非精确匹配两个领域的重要算法进行分析的基础上,提出了一个高效的候选集过滤算法HLMA。实验证明,该算法既能满足尽量缩小候选集的过滤要求,又能兼顾过滤的时间效率。本文所描述的工作具有一定的创新性。其中,在与目前公认的最快图匹配算法TurboISO所进行的对比实验中,Tps算法具有明显的执行效率优势。更重要的是Tps算法的效率优势来自于更合理的理论基础,即本文所提出的MSGM模型可以指出何为最优的顶点搜索顺序。由此导出的两大关键点可以从理论上解释目前若干主要算法的相似相异之处,从而得出与相关对比试验结果相一致的经验结论。在此基础上提出的伪树估计法跳出了前人算法的藩篱,是Tps算法优异性能的根基所在。总而言之,MSGM模型为子图搜索算法进一步的研究提供了一个蓝图,而Tps算法是该蓝图下的一个初步尝试。