algorithm - 计算子图实例

Question

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

Answer 1

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

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