查找图中所有完整的子图

Question

是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向、未加权的图，我需要找到其中的所有子图，其中子图中的每个节点都连接到子图中的每个其他节点。

有现成的算法吗？

Answer 1

这被称为 派系问题;这很困难，而且一般来说是 NP 完全的，是的，有很多算法可以做到这一点。

如果图表具有其他属性（例如它是二分的），那么问题就变得相当容易，并且可以在多项式时间内解决，但否则它就非常困难，并且仅对于小图才能完全解决。

来自维基百科

在计算机科学中，派问题是指与在图中查找特定完整子图（“派”）相关的任何问题，即每对元素相连的元素集。

派系问题包括：

• 找到最大派（具有最多顶点数的派），
• 在加权图中找到最大权重团，
• 列出所有最大派系（无法扩大的派系）
• 解决测试图是否包含大于给定大小的团的决策问题。

这些问题都很困难：团决策问题是 NP 完全问题（卡普的 21 个 NP 完全问题之一），找到最大团的问题既是固定参数棘手的又难以近似，并且列出所有最大团可能需要指数时间，因为存在图具有指数级数量的最大派系。然而，针对这些问题的算法可以在指数时间内运行，或者在多项式时间内处理某些更专门的输入图。

也可以看看

• 布隆-克博什算法

Answer 2

井尺寸的图中发现的k顶点子n的问题是复杂的

  

为O（n-1K-K ^ 2）

由于有n^k子图，以检查和他们每个人都有k^2边缘。

什么你所要求的，发现在图中的所有子图是一个NP完全问题和上面列出的布隆-Kerbosch算法进行说明。