我有一个无向图G。由于G是顶点和边的集合，我想将其视为"数据库"。
现在我有一个查询图H，保证是G的子图。我如何确定H对应于G的哪个部分？
这个问题与这里现有的问题不同，因为基本上我肯定知道H是G的一部分。
查找一个图是否是另一个图的子图，即子图同构问题是NP完全的。许多图形处理系统使用的解决此问题的方法是图形索引。它减少了必须超过子图同构测试的候选图的数量。索引创建有很多变化，对此有很多研究，也有很多论文可用。这些是我发现有用的一些示例论文：图形索引：一种常见的基于 Strucutre 的方法 - 这是一个相当古老的方法，但这个问题得到了很好的解释，非常有益于阅读。GRAPES：一款用于在生物图谱上进行并行搜索的软件 - 这也值得一读，它很好地解释了图索引过程。
这是子图同构问题。如果您不限制查询图，则它是NP完全的（因为您可以将H取为哈密顿循环）。如果图形 H 非常小（固定），您可以在多项式时间内在 G 中找到 H 的副本（通过简单的蛮力，或通过维基百科页面中提到的算法）。