计数子图实例

Question

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

Answer 1

虽然图同构在一般情况下是NP-完全的，但在现实世界中遇到的问题通常是相当容易的。一个简单的蛮力就足够了:让M_i是一组映射，从G的第一个i节点到G的节点，从包含空映射的m_0开始，每次扩展一个节点，丢弃任何违反约束x->y的映射。

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