是否有已知的算法或方法可以在图中找到所有完整的子图？我有一个无向、未加权的图，我需要找到其中的所有子图，其中子图中的每个节点都连接到子图中的其他节点。
有没有现成的算法呢？
问问题
21811 次
2 回答
21
这被称为集团问题；这很难，而且通常是 NP 完全的，是的，有很多算法可以做到这一点。
如果图有额外的属性（例如它是二分图），那么问题会变得相当容易，并且可以在多项式时间内解决，但否则非常困难，并且仅对于小图完全可以解决。
来自维基百科
在计算机科学中，集团问题是指与在图中找到特定完整子图（“集团”）相关的任何问题，即每对元素相连的元素集合。
集团问题包括：
- 找到最大团（顶点数最多的团），
- 在加权图中找到最大权重团，
- 列出所有最大团（不能扩大的团）
- 解决测试图是否包含大于给定大小的团的决策问题。
这些问题都很困难：团决策问题是 NP 完全问题（Karp 提出的 21 个 NP 完全问题之一），寻找最大团的问题既难以固定参数也难以近似，列出所有最大团可能需要指数时间，因为存在具有指数数量的最大团的图。然而，有一些算法可以在指数时间内运行，或者在多项式时间内处理某些更专业的输入图。
也可以看看
于 2010-05-10T08:02:12.620 回答
3
那么在大小为 n 的图中找到 k 顶点子图的问题很复杂
O(n^kk^2)
因为有n^k要检查的子图，并且每个子图都有k^2边。
您所要求的，在图中查找所有子图是一个 NP 完全问题，并在上面列出的 Bron-Kerbosch 算法中进行了解释。
于 2018-08-07T15:05:30.617 回答