子图匹配的前提是图分类吗

不是图分类。

实现的子图匹配算法，都一般会采用下述两种框架之一：

直接枚举框架（direct-enumeration framework）：此类子图匹配算法不会提前产生辅助索引结构进行预处理，而是在枚举的过程中通过一些过滤策略对候选点进行剪枝，因此在枚举过程中是直接访问原数据图来匹配查询图的顶点和边的。

索引枚举框架（indexing-enumeration framework）：此类子图匹配算法会对数据图和给定的查询图进行预处理，生成辅助索引结构维护候选顶点和候选顶点之间的侯选边，在枚举过程中，匹配查询图的顶点和边时会访问这个索引结构而不是直接访问原来的数据图，这可以减少许多无效的访问。

在研究图匹配问题中，我们经常会碰见图同构的概念。这篇文章就来看看图同构是什么。

考虑两张图，图同构是指存在一个双射，它满足1）映射后的顶点的标签和映射之前的顶点的标签一致，2）如果任意顶点对之间存在连边，那么映射后的顶点对之间也会存在连边，3）如果映射后的顶点对之间存在连边，那么映射前的顶点对之间也存在连边。

图同构问题是少数几个要么是P要么是NP完整的问题，因而它在计算复杂度研究中十分受关注。

图同构可以视为图”相等“的一种定义,子图同构则可视为子图“相等”。子图同构问题是一个NP完整问题。解决子图匹配问题通常依靠启发式搜索。

图同构关注保结构的映射，图同态关注保连接的映射。如果一个同态变换是一个双射且它的逆映射也是一个同态，那么它一定是一个同态。类似子图同构，我们可以定义子图同态。

---