graph-theory - 找到与查询图匹配的子图？

Question

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

现在我有一个查询图H，它保证是G. 我怎样才能弄清楚H对应于哪个部分G？

这个问题与这里的现有问题不同，因为基本上我知道肯定H是G.

Answer 1

查找一个图是否是另一个图的子图，即子图同构问题是NP完全的。许多图形处理系统使用的解决此问题的方法是图形索引。它减少了必须超过子图同构测试的候选图的数量。索引创建有很多变体，对此有很多研究，也有很多论文可用。这些是我发现有用的一些示例论文： 图形索引：一种常见的基于结构的方法——这是一个相当古老的方法，但是这个问题得到了很好的解释，非常有利于阅读。 GRAPES：用于并行搜索生物图的软件- 这也值得一读，它很好地解释了图索引过程。

Answer 2

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