找到与查询图匹配的子图？

Question

我有一个无向图G。因为G是一个顶点和边的集合，所以我想把它当作一个“数据库”。

现在我有了一个查询图H，它保证是的一个子图。如何计算出H对应于G的哪一部分

这个问题不同于这里现有的问题，因为我基本上知道H是G的一部分。

Answer 1

判定一个图是否是另一个图的子图，即子图同构问题是NP-完全的。许多图形处理系统使用的一种方法就是图表索引。它减少了必须超过子图同构测试的候选图数。索引的创建有很多不同的形式，对此有很多的研究，也有很多的论文。以下是一些我发现有用的示例论文：图形索引:一种基于频繁结构的方法 --这是一个非常古老的问题，但问题确实得到了很好的解释，非常有益于阅读。GRAPES:生物图形并行搜索软件 --这也是值得一读的，它很好地解释了图表索引的过程。

Answer 2

这是子图同构问题。如果你不限制你的查询图，它是NP-完全的(因为你可以取一个哈密顿循环H)。如果图H非常小(固定)，则可以在多项式时间内(通过简单的蛮力或维基百科页面中提到的算法)在G中找到H的副本。