问题标签 [clique]

谁能告诉我，在网上哪里可以找到 Bron-Kerbosch 算法的解释，或者在这里解释它是如何工作的？

我知道它发表在“算法 457：找到无向图的所有派系”一书中，但我找不到可以描述该算法的免费资源。

我不需要算法的源代码，我需要解释它是如何工作的。

图是图的子图，其中任何顶点与其余顶点相连。

在 k- 问题中，输入是一个无向图和一个数字 k，如果存在，则输出是一个大小为 k 的 clof（或者，有时，所有大小为 k 的 cl）

Android 接口上的网络接口被列为/sys/class/net/文件系统中的目录。

对于大多数 Android 设备，gprs 流量的网络接口称为rmnet0，而对于 Wi-Fi，它通常是eth0或tiwlan0。

我怀疑摩托罗拉 CLIQ XT 的单元接口是rmnet0，但我想确认一下 + 知道 Wi-Fi 接口的名称。

此外，最好知道此型号的设备 ID。这是Java SDK 中作为android.os.Build.DEVICE可用的值。（例如 T-Mobile G1 使用dream，Samsung Galaxy 使用GT-I7500，Motorolda Droid 使用sholes。）

我想知道一种快速算法，只找到大约 100 个顶点的图的团数（实际上没有找到团）。

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

一种快速算法，可以在具有大约 100 个顶点的完美图中找到最大团的大小（这个具有至少 1 个弦的奇数循环）？

有没有比蛮力更简单的方法，因为这是一个完美的图，应该有一个多项式时间解决方案。但我找不到算法。

贪婪着色是否会在所有完美图形中提供最佳着色？

我遇到了一个特定的问题，并为它寻找一些算法。要解决的问题如下所述。

假设我们有如下组合

1 - 3 - 5

1 - 4 - 5

1 - 8 - 5

2 - 4 - 5

3 - 4 - 5

2 - 4 - 7

这些组合是从给定的集合中生成的，在这种特殊情况下，让我们说

{1},{3,4,8},{5}

{2,3},{4},{5}

{2}、{4}、{7}

我想做的是从这些组合中重新创建集合。我知道对于这些组合，您有不止一种解决方案，例如

第一个解决方案

{1}、{3、4、8}、{5}

{2, 3}, {4}, {5}

{2}、{4}、{7}

第二种解决方案

{1}、{3、8}、{5}

{1、2、3}、{4}、{5}

{2}、{4}、{7}

第三个解决方案

{1}、{3、4、8}、{5}

{3}、{4}、{5}

{2}、{4}、{5、7}

但是最终（最佳）解决方案将是具有尽可能少的集合的解决方案，或者是随机解决方案，以防它们在集合计数方面都相等。

是否存在针对此类问题的算法？如果任何一直在处理此类问题的人可以给我一些提示，我将不胜感激。

编辑：看起来我正在寻找的是 n 元积的分解（N 的笛卡尔积）

编辑：在对该主题进行更多研究后，我发现该问题在“图论”中被称为“最小集团覆盖”问题

问候，巴兹

简而言之，我的幼稚代码（在 Ruby 中）看起来像：

还有我的 Bron Kerbosch 实现：

我还实现了旋转和退化排序，这减少了 bron_kerbosch 的执行时间，但不足以超越我最初的解决方案。情况似乎是错误的；我缺少什么算法洞察力？如果您需要查看完整的工作代码，这里有一个更详细的文章。我已经在大小达到一百万左右的伪随机集上对此进行了测试。

BK clique 的维基百科伪代码通过旋转找到：

我不清楚 P union X 是空的会发生什么。由于 u 是未定义的，函数是否继续以 N(u) 作为空集（即它继续为 P 中的每个顶点 v），还是返回给调用者？

我有这个问题，我需要帮助，这是我的代码：

首先我在我的图表中搜索以找到派系，然后我测试长度为 3 的派系，如果它是真的我想删除一条边所以我可以消除完整图（3）。我怎样才能做到这一点？

谢谢

给定一个分布在 6 个维度上的 23 个点的数据集，在本练习的第一部分中，我们应该执行以下操作，而我被困在后半部分：

• 计算 CLIQUE 算法的第一步（检测所有密集单元）。在域 0..100 中每个维度使用三个相等的间隔，如果一个单元格包含至少五个对象，则认为它是密集的。

现在这是微不足道的，只是一个计数的问题。下一部分询问以下内容：

• 确定一种仅使用 Preprocess、Classify、Cluster 或 Associate 选项卡中提供的 Weka 功能来计算上述 CLIQUE 结果的方法。 提示：只需要两个选项卡。

我已经尝试了一个多小时，但我似乎无法在这里找到解决方案。如果有人有提示，或者可能是有用的教程，可以让我对 weka 有更多的了解，我们将不胜感激！