问题标签 [clique]

igraph 包允许我们相当简单地识别图中的集团（https://igraph.org/r/doc/cliques.html）。它返回顶点列表。但是，我需要简单地计算最大集团的大小。在文档中，它提到可以计算最大集团的大小，但没有为此任务提供函数。

关于派系主题的其他主题似乎集中在识别最大派系，找到满足特定标准的最大派系，计算特定大小的非重叠派系等。但我没有发现任何关于简单报告大小的信息的最大集团。

有谁知道如何计算图中最大集团的大小（顶点数）？

我试图在图中找到最大集团（邻接矩阵），该图最多可以有 50 个节点。目前，当图形大小达到 n = 40 左右时，我已经开始永远花费。谁能找到我可以做的任何优化？

全类内容：https : //pastebin.com/fNPjvgUm 邻接矩阵：https ://pastebin.com/yypN9K4L

我在 spyder 中完成了以下代码：

我有 69 个对象，nx.enumerate_all_cliques可以从 excel 文件中找到所有 47000 种可能的兼容组合。我在此列表中有某些必须在一起的对象，我想忽略所有不包含该可能组合中某处所有对象的组合。我可以列出必须放在一起的项目组，因为只有少数。

我正在尝试编写一个代码，它将通过有限无向图的边缘着色有限地表示完整无限图上的边缘着色，然后尝试使用这些有限表示找到一些拉姆齐数的上限。

我感兴趣的 Ramsey 数是 $R(\alpha, k)$ 的形式，其中 $\alpha$ 是可数的，k 是有限的。为简单起见，我有兴趣在不包含单色 k 团的有限无向图上生成所有可能的边缘着色。假设我们将有限图的边着色为两种颜色（即红色和蓝色），再次为简单起见，如果着色在它们之间分配了蓝色边而不是边，则在两个节点 n1 和 n2 之间放置一条边如果着色在它们之间分配了红色边缘，则在它们之间；问题归结为：如何在不包含 k 团的 n 个顶点上有效地生成所有可能的无向图？

我认为我可以使用 networkx，因为它是我习惯的唯一与图形相关的库，但是，我想不出一种简单的方法来在 networkx 中进行这一生成。我也愿意使用任何语言的任何库来有效地解决这个问题，因为，正如你可能猜到的，有一天这个 n 将是一个很大的数字......

感谢您的时间

在图中找到可以使用 n 个节点和 e 个边形成的团的最小可能大小。该组件应该是一个完整的图形。

换句话说，找到顶点子集的最小大小，使得每两个不同的顶点在它的所有节点之间都有一条唯一的边。

• 给定的图被认为是无向的。
• 大小是指派系中的节点数。

例子：

• 给定 5 个节点和 6 条边，完整图的最小尺寸为 2（可视化）
• 给定 5 个节点和 7 条边，完整图的最小尺寸为 3（可视化）

我有一个超过 90000 个节点的网络。我想检查它是否有 5 个或更多成员的派系（=其中每个节点都连接到该集合的所有其他节点的节点集）。NetworkX 库中是否有一个命令可以为我的网络返回所有此类集团？

我试过了

但由于网络的规模，运行时间是不可接受的，这就是为什么我想设置 5 个或更多成员的阈值，这有望减少运行时间，因为将考虑更少的派系。

我正在研究 Clique 问题和算法。然后我看到了。正如本文所说，我们可以在 O(n^2) 时间复杂度中找到最大团。我是不是误会了什么，或者这是 P=NP 的证明？

我正在尝试使用 Prolog 解决一些关于图论和网络分析的任务。给定一个带有节点和连接的图：

我必须添加谓词检查一个节点是否连接到另一个节点。这是我的代码：

现在我必须编写一个谓词来检查某个图是否是一个集团。因此，根据集团的定义，所有节点是否相互连接。

如果有人对如何解决这个问题有任何建议，我很想听听。

我想k在无向图中找到所有大小的集团。这个问题描述了一个类似的问题；与链接问题中的 OP 不同，我对查找所有派系不感兴趣，只对 size 的派系感兴趣k。

到目前为止，我发现了两种方法。首先是按规模递增的顺序处理所有派系。第二个是计算所有最大派系，获取大小子集n并删除重复项。

每种方法都有缺点并且在某些情况下是不切实际的。有没有更好的方法来找到给定大小的所有派系？

方法 1：按大小递增的顺序遍历列表。

方法 2：生成最大派系并找到大小的唯一子集k。

我有一个 Python 程序，它必须将节点和图形的数量发送到 C 程序以进行更快的计算（称为 cliquer）。C 程序（可执行文件更好，因为它应该更快）然后计算团并将它们返回给 Python，Python 计算其他参数。我创建这样一个自动管道非常重要，因为计算过程非常慢。我浏览了互联网，发现的所有内容都是基于 Linux 的。