代码之家 › 专栏 › 技术社区 › dsimcha

计数子图实例

isomorphism np-complete graph-theory graph algorithm

5

dsimcha · 技术社区 · 14 年前

假设我有一个大的(几千个节点)有向图克一个更小的(3-5节点)有向图克 . 我想数一数克在克 . 换句话说,我想知道克比赛克 . 我知道这是子图同构问题的一个例子,因此是NP完全的。但是,考虑到你可能认为克很小,有没有合理有效的算法来做这个?

1 回复 | 直到 14 年前

1

Keith Randall 14 年前

尽管图同构一般是NP完全的,但在现实世界中遇到的问题通常是相当容易的。一个简单的暴力就足够了:让 M_i 是一组从g的第一个i节点到g的节点的映射 m_0 包含空映射并一次扩展一个节点,丢弃任何违反约束的映射 x->y 敌我识别 m(x)->m(y) .

您需要将节点按g排序,以便及早进行大量修剪。假设您的图非常稀疏,那么您需要一个尽早完成尽可能多边的顺序,可能是来自最高阶节点的dfs。