问题标签 [clique]

我正在研究 NP 课程，其中一张幻灯片提到：

是否曾经证明，CLIQUE 的补语是否是 NP 的一个元素？

另外，你有证据吗？

维基百科上显示的图形模型中的最大集团 仅包括大小为 3 和 4 的集团。但我认为根据上述定义，2 号规模的集团（连接 3,4 号规模的集团）也应包含在最大集团中。如果我错了，任何人都可以纠正我。

我想使用 R 包的 igraph 为图形打印派系。我要打印为 ABC 的数据格式（以 Res1、Res2、Res3 格式显示此数据...）

数据： Res1 Res2 重量 AB 10 AC 1 CB 10 SB 1 LA 2

如果我们想在终端上打印 Cliq

克利克

[[1]] + 3/5 个顶点，命名为：[1] ACB

这一切都很好。但是如果我们想打印到文件：

但是文件的结果是： V1 c(1, 2, 5)

我想打印数据作为节点名称 AB C. 什么是出路的家伙..!!

是否存在用于计算无向图中所有k 团的顺序算法？

对于 k-cliques，我的意思是：在无向图中通过边相互连接的顶点集的数量。

在这里可以找到更详细的集团描述。https://en.wikipedia.org/wiki/Clique_(graph_theory)

我想在连通图中找到包含某个顶点的最大集团。在 wiki 中，它说可以通过贪婪搜索找到最大集团。但是，这并不能确保您找到最大的集团 IMO。例如，

如果我想找到包含 A 的最大集团，并且我通过贪婪搜索来做到这一点，我最终可能会找到 (A,B)，它小于另一个集团 (A,C,D)。

我想出了一个避免更小的团的天真的方法：首先找到与您的起点相邻的所有顶点，然后对于这些顶点中的每一个（我们称之为 x），计算 x 不相邻的其他顶点的数量。之后，删除与大多数顶点不相邻的顶点，并检查其余顶点是否形成一个团。如果没有，请重复该过程，直到其余的人形成一个集团。

我知道这是一个愚蠢的问题，但如果有人能告诉我这种方法是否正确，我将不胜感激。

我读到完美图的最大独立集可以在多项式时间内找到。

是否有任何多项式时间算法可以找到完美图的所有独立集的列表？

我正在尝试为一组项目找到最大的集团。

目前我正在使用python的networkx库并使用find_cliques（）函数来查找所有最大派系，如下所示：

但我实际上期望的是找到最大团，然后删除最大团图中的节点，然后再次从先前删除后留下的节点中找到最大团。

对于上面的例子，我希望得到 [2, 1, 3, 4] 然后删除这些节点，所以只剩下 5 和 6 ，这将是另一个集团 [5, 6] 。

更新

我们可以使用G.remove_node()，它按预期删除节点以及所有相邻边。

但是每次删除节点时，都会找到新的最大团并将其存储在新列表中，依此类推。如何在 while 循环中运行，直到图 G 中没有边，即节点数为 0 或 1。

我有以下形式的字典

每个值（未排序的列表）对应于我想在我的图表中引入的一个集团。不幸的是，如您所见，许多派系共享顶点，这些顶点也是其他派系的一部分。现在，我对这些派系进行了直接的诱导：

但这在某种意义上是耗时的，因为许多边对已经作为其他集团归纳的一部分而较早地被引出。有没有更有效的方法来诱导这些集团？也许对这些集团本身进行一些后期处理？

我试图在图中找到所有最大派系，而不会重叠。该函数max_cliques()返回图中所有可能的最大派系，但我希望每个顶点仅包含在一个派系中 - 在它可以成为的最大派系中。

例如，如果 的输出max_cliques()是以下派系：

{A,B,C}, {A,B,D}, {A,B,J,K}, {E,F,G,H}, {E,F,G,I}

我想删除一些派系，以便所有顶点都出现在一个派系中，所以最终的集合将是：

{A,B,J,K}, {E,F,G,H}

A 和 B 包含在 3 个 cliques 中，所以我想选择 cliques 以使最终集合包含尽可能多的顶点。如果有相同长度的两个可能的派系 - 随机选择一个。（我不介意不包括所有顶点）

我真的很感激一个解决这个问题的想法，即使没有深入了解派系的细节——问题基本上是如何删除包含重叠元素的最短“列表”。

提前致谢

我正在尝试编写一种算法来计算输入图（无向且无自环）的边缘团覆盖数（覆盖所有边缘的最小团数）。我的想法是

1. 使用Bron-Kerbosch算法计算所有最大团，以及
2. 尝试其中任何 1,2,3,... 是否会覆盖所有边缘，直到我找到最小数量

那行得通吗？有人知道更好的方法吗？有标准算法吗？令我惊讶的是，我找不到任何这样的算法。我知道这个问题是 NP 难的，所以我不希望有一个快速的解决方案。