计算子图实例

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。