图的集团数 [英] clique number of a graph

问题描述

我想知道一种快速算法，该算法仅查找具有约100个顶点的图的团数（实际上未找到团）。

I would like to know a fast algorithm to find only the clique number(without actually finding the clique) of a graph with about 100 vertices.

我正在尝试解决以下问题。
http://uva.onlinejudge.org/external/1/193。 html

I am trying to solve the following problem. http://uva.onlinejudge.org/external/1/193.html

推荐答案

这是NP完全的，并且比实际找到最大值要好得多集团并计算其顶点。来自维基百科：

This is NP-complete, and you can't do it much better than actually finding the maximum clique and counting its vertices. From Wikipedia:

集团问题包括：

Clique problems include:

• 解决测试图是否包含大于N的集团的决策问题。

这些问题都很棘手：集团决策问题是 NP -complete（Karp的其中之一） 21 NP -完全问题），

These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems),

如果可以找到集团编号在 P 中，则决策问题在 P 中可以回答（您只需计算集团数字并将其与<$进行比较即可）。 c $ c> N ）。

If you can find the clique number in P, then the decision problem is answerable in P (you simply compute the clique number and compare it with N).

由于决策问题是 NP完成 ，找到一般图形的集团号必须为 NP-Hard 。

Since the decision problem is NP-Complete, finding the clique number of a general graph must be NP-Hard.

这篇关于图的集团数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！