问题描述
是否存在已知的算法或方法来查找图中的所有完整子图?我有一个无向，无权的图，我需要在其中找到所有子图，其中子图中的每个节点都与子图中的每个其他节点相连.
Is there a known algorithm or method to find all complete sub-graphs within a graph? I have an undirected, unweighted graph and I need to find all subgraphs within it where each node in the subgraph is connected to each other node in the subgraph.
是否存在用于此目的的算法?
Is there an existing algorithm for this?
推荐答案
这被称为 clique问题;这很困难，而且一般来说都是NP完全的，是的，有很多算法可以做到这一点.
This is known as the clique problem; it's hard and is in NP-complete in general, and yes there are many algorithms to do this.
如果图具有其他属性(例如，它是二分图)，则该问题变得非常容易并且可以在多项式时间内解决，但否则非常困难，并且仅对于小图是完全可解决的.
If the graph has additional properties (e.g. it's bipartite), then the problem becomes considerably easier and is solvable in polynomial time, but otherwise it's very hard, and is completely solvable only for small graphs.
集团问题包括:
- 找到最大的集团(具有最大数量的顶点的集团)，
- 在加权图中找到最大权重集团
- 列出所有最大集团(无法扩大的集团)
- 解决测试图形是否包含大于给定大小的集团的决策问题.
- finding the maximum clique (a clique with the largest number of vertices),
- finding a maximum weight clique in a weighted graph,
- listing all maximal cliques (cliques that cannot be enlarged)
- solving the decision problem of testing whether a graph contains a clique larger than a given size.
这些问题都很棘手:集团决策问题是NP完全问题(Karp的21个NP完全问题之一)，找到最大集团的问题既是固定参数难解决的又难于近似，并且列出了所有最大值团可能需要指数时间，因为存在具有成倍增长的最大团的图.尽管如此，仍有一些针对这些问题的算法可以在指数时间内运行，或者可以在多项式时间内处理某些更专业的输入图.
These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems), the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.
另请参见
- Bron-Kerbosch算法
- Bron–Kerbosch algorithm
See also
这篇关于查找图中的所有完整子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！