给定无向图中存在多少个完整图? [英] How many Complete Graph present in given undirected Graph?

问题描述

是否存在一种已知的算法来查找图中的所有完整子图?我有一个无向图，我需要找到该无向图中存在的所有完整图.

Is there a known algorithm to find all complete sub-graphs within a graph? I have an undirected, graph and I need to find all complete graphs present in that undirected graph.

是否存在用于此目的的算法?

Is there an existing algorithm for this?

推荐答案

在无向图中找到完整子图的数目称为 clique问题.它在多项式时间内是不可解的，因为完整的子图本身的数量可能是指数的.因此，没有一种算法可以在合理的时间内解决任何大小的图形的问题.但是，我发现这是一种适用于小型图的方法:

Finding the number of complete subgraphs in an undirected graph is known as the clique problem. It is not solvable in polynomial time, since the number of complete subgraphs itself might be exponential. Therefore, there is not an algorithm that will solve this for graphs of any size in a reasonable amount of time. However, here is one I found that should work for small graphs:

https://en.wikipedia.org/wiki/Bron%E2 ％80％93Kerbosch_algorithm

这篇关于给定无向图中存在多少个完整图?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！