algorithm - 计算子图实例

Question

假设我有一个大的（几千个节点）有向图G和一个小得多的（3-5 个节点）有向图g。我想计算在G中有多少g的同构。换句话说，我想知道 G 中有多少独特的节点集与g匹配。我意识到这是子图同构问题的一个实例，因此是 NP 完全的。但是，鉴于您可能假设g很小，是否有任何合理有效的算法可以做到这一点？

Answer 1

尽管图同构通常是 NP 完全的，但您在现实世界中遇到的问题通常很容易。一个简单的蛮力就足够了：让M_i一组从 g 的第 i 个节点到 G 的节点的映射。从m_0包含空映射开始，一次扩展一个节点，丢弃任何违反约束x->yiff的映射m(x)->m(y)。

您需要对 g 中的节点进行排序，以便尽早进行大量修剪。假设您的图表非常稀疏，您将需要一个尽可能早地完成尽可能多边的订单，也许是来自最高度节点的 dfs。