问题标签 [clique-problem]

CLIQUE 问题——在图中找到最大团的问题是 NP 完全的。也就是说，CLIQUE 是

a.) 在 NP 和 b.) 中存在一个 NP 完全问题，一个 3-SAT，在多项式时间内简化为 CLIQUE。

上面的（b）部分很好——在每一个资源中都有，而且解释得很好。对于 (a) 部分，据我所知，我们需要具备以下条件：给定一个特定的解决方案实例，我们需要证明可以在多项式时间内验证该解决方案是该问题的答案。因此，例如，给定一个特定的图和它的子图，我们应该能够检查该子图是否是该图中最大尺寸的集团。

到目前为止，我阅读的资源将这部分 (a) 表述为“简单、直接等”或“可以在 O(n^2) 时间内显示给定子图是一个集团/不是”。但是，这里的验证不仅仅是它是否是一个团，而是它是否是图中的一个最大团。这如何在多项式时间内决定？

我在这里想念什么？

我仍然面临一个最喜欢的按钮，它应该保存我的布局并将布局设置为新活动的布局。问题是我的活动应该打开我保存的布局，但我没有这样做'不明白为什么..这是我的代码：

这是保存布局的代码：

非常感谢 ！

LE：我为应该打开已保存布局的活动编辑了第一个代码，但按钮仍然打开一个黑色活动..

我一直在尝试用下面提到的算法解决最大集团问题，但到目前为止还没有找到失败的情况。
算法：
对于给定的图，每个节点从 1 到 N 编号。
1. 将节点视为永久节点并形成一组节点，使得每个节点都连接到该永久节点。（该集合也包括永久节点）
2 . 现在形成原始图的子图，使其包含所形成的集合中的所有节点，并且仅包含在集合中存在的节点之间的那些边。
3. 求每个节点的度数。
4. 如果所有节点的度数相同，则我们有一个集团。
5. 否则从该子图中删除最小度数节点并从步骤 3 开始重复。
6. 对图中的所有节点重复步骤 1-5。

谁能指出这个算法的缺陷？
这是我的代码 http://pastebin.com/tN149P9m。

我有一个要解决的问题，我想实现一个方法，该方法采用一个集团并返回包含该集团的最大集团。我正在研究的方法是递归的，并使用回溯来根据集团定义接受或拒绝解决方案。我的问题是我不想使用 Bron-Kerbosch 算法，因为我只想将一个参数传递给该方法。这是我所做的伪代码：

你能帮我想想如何选择打破递归的条件吗？我不知道如何将下一个候选者的值保持到下一个循环而不将其传递给方法参数！

我想编写用于邻接矩阵的最大团算法。我正在观看一段视频，该视频解释了如何使用 Python 编写和实现算法。我目前正在尝试在视频 2 分钟后对 powerset 功能进行编码。

我想用 C++ 重写它。我不确定我是否应该使用数组。到目前为止，我已经编写了以下代码，但我不知道如何在空数组中返回一个空数组（当elts list大小为 0 时）。

我为数组编写了一个isEmpty函数，因为我不能len(elts)像在 Python 中那样使用。我的方法可能不是最好的方法，所以我愿意接受任何建议。

更新：

在我的 int main 我有：

我不知道从这里做什么。

代码应该使用我们称之为“elts”（元素的缩写）的array// 。然后首先，它应该添加空列表，然后是电源集的其余部分（全部显示在视频中）。listvector[]

例如，在这种情况下elts = [1,2,3,4]，我的代码应该返回：

我不知道如何使用array//来做上面的事情list。vector

是否有任何软件或算法描述可以让您在具有约 17000 个加权顶点和约 75% 密度的图中找到具有已知顶点数的最大团（大约）？我尝试使用 Cliquer，但它太慢了（让我几天才能得到结果）。

关于我的问题，以防万一 - 这是一个时间安排问题，我有 18 个时间段，每个时间段都可以由不同数量的替代方案填充。每个变量代表一个插槽的一个备选方案。因此，一个插槽的所有替代方案都是互斥的，并且不同插槽的一些替代方案是不兼容的。如果两个备选方案兼容，那么它们之间就有优势。权重代表备选方案的价值。

在为这个问题苦苦挣扎了一段时间后，我希望在这里得到一些建议。我想知道是否有人知道基于重要性确定成对分组标签的自动化方法。该问题与显着性检验无关（例如 Tukey 用于参数或 Mann-Whitney 用于非参数） - 考虑到这些成对比较，一些箱线图类型的图通常用下标表示这些分组：

我手工完成了这个例子，这可能很乏味。我认为算法中的标记顺序应该基于每个组中的级别数 - 例如，应该首先命名包含与所有其他级别显着不同的单个级别的组，然后是包含 2 个级别的组，然后是 3 个，等等，同时检查新分组是否添加了新的所需分组并且不违反和差异。

在下面的示例中，棘手的部分是让算法识别级别 1 应与 3 和 5 分组，但不应将 3 和 5 分组（即共享一个标签）。

示例代码：

我想在一个中等大小但密集连接的图中找到所有派系，该图中有 369 个节点和 22,724 条边。Graph.cliques()首先我简单的通过python接口调用了igraph的方法：

它仍在运行，并且在 i7-4600U 内核上消耗了超过 3 小时的净 CPU 时间。因此，我开始关注其他可能性，并且我记得几年前我已经使用了一个很好的代码。它被称为 justTheCliques，可在此处获得：https ://github.com/aaronmcdaid/MaximalCliques 。描述说：

在边缘列表上运行 Bron-Kerbosch 算法

运行此算法会在几秒钟内在同一图表上给出结果：

我喜欢igraph，我只想知道，这背后的本质原因是什么？Igraph 使用不同的算法？结果应该是一样的吧？

我需要遍历图像中彼此相邻的所有（无序）像素对而不重复。我正在使用 8 点邻域。例如：

像素f的邻居在它周围的 3x3 正方形中。因此，例如g与f形成一个 2 点团。如果我要遍历图像的所有行和列，这个团将被计算两次，一次是f是中心像素，一次是g是中心像素。其他派系也会出现类似的低效率。

所以我想做的是循环遍历所有的派系，而不是每个像素。如果我熟悉图论，我认为已经对类似问题给出的一些答案就足够了，但由于我不是，我真的很感激你可以用外行的有效算法提供的任何帮助。提前致谢！

假设给你一个黑盒子，它可以在恒定时间内解决一个派系问题。

你给黑盒子一个有界 k 的无向图 G，它输出“是”或“否”，即图 G 有一个至少有 k 个顶点的团。

你将如何使用这个黑盒在多项式时间内找到最大团的顶点？