是否有已知的算法或方法来查找图中的所有完整子图？我有一个无向、未加权的图，我需要找到其中的所有子图，其中子图中的每个节点都连接到子图中的每个其他节点。
有现成的算法吗？
这被称为派系问题 http://en.wikipedia.org/wiki/Clique_problem;这很困难，而且一般来说是 NP 完全的，是的，有很多算法可以做到这一点。
如果图具有额外的属性（例如，它是二分图），那么问题就会变得相当容易，并且可以在多项式时间内解决，但否则就非常困难，并且仅对于小图才能完全解决。
来自维基百科
在计算机科学中，派问题是指与在图中查找特定完整子图（“派”）相关的任何问题，即每对元素相连的元素集。
派系问题包括：
- 找到最大派（具有最多顶点数的派），
- 在加权图中找到最大权重团，
- 列出所有最大派系（无法扩大的派系）
- 解决测试图是否包含大于给定大小的团的决策问题。
这些问题都很困难：派系决策问题是 NP 完全问题（卡普的 21 个 NP 完全问题之一），找到最大派系的问题既是固定参数棘手的又难以近似，并且列出所有最大派系可能需要指数时间，因为存在具有指数数量的最大派系的图。然而，针对这些问题的算法可以在指数时间内运行，或者在多项式时间内处理某些更专门的输入图。
See also
- 布隆-克博什算法 http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
