问题标签 [clique-problem]

我遇到以下问题：

我有一个包含多个选项卡的报告，其中一个选项卡中有一个名为“Employees”的表，其中包含改变该表的不同过滤器，以及与“Employees”表交互的其他图形，例如“英语水平”。同样，在第一个选项卡中，我创建了一个钻取（获取详细信息），它将我从“员工”表带到报告的其他选项卡。

关键是，当你通过“英语水平”图进行过滤时，“员工”表发生了变化，它被赋予获取另一个选项卡的详细信息，当你返回“员工”表所在的原始选项卡时，它叶子被图表“英语水平”过滤

有什么办法可以解决吗？从某种意义上说，当返回选项卡时，图表的选择仍然处于活动状态？

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

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

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

感谢您的时间

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

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

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

例子：

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

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

我有一个作业问题，要求使用多项式算法来找到一个大小为 Ω(logn) 的集团。

我目前的实现如下：

1. 将图划分为 n^logn 个大小为 logn 的微集（子图）并将它们存储为邻接矩阵
2. 对于每个子图，蛮力检查 S 是否为大小为 logn 的集团
3. 如果 S 是一个集团，则返回它。
4. 如果我们在没有找到 clique 的情况下完成迭代，则返回 None（图中没有 logn cliques，这是最坏的情况）

构建子图将花费 n^k 时间。要检查一个子图是否是一个大小为 logn 的 clique 将花费 O((logn)^2)，因为子图中的每个顶点将有 k^2 个边（其中 k 是 clique 的大小，在这种情况下是 logn）。这必须对所有 n^logn 子间隙进行，因此总运行时间为 O(n^logn +(n^(logn))((logn)^2))。

我的问题是：

1. 这是多项式，还是 k 作为指数使其成为指数
2. 我的逻辑合理吗？
3. 运行时间减少到什么程度？

谢谢大家！

编辑 1：我意识到在多项式时间内做到这一点的唯一方法是不创建 n^k 子图，而是将图划分为 n/k 个分量。但是，如果我这样做，则无法保证我的任何微集实际上都会有一个 k 大小的团，即使图中保证了一个。有没有办法解决？

编辑 2：我之前没有提到或考虑过的一件非常重要的事情是，我们得到 G 的集团规模为 n/2。因此，我们知道将 G 分成大小为 logn 的 n/logn 个子集的最坏情况将是当 n/2 的最大团被均匀地分成大小为 logn/2 个的团到每个子图中时。这保证了我们至少找到一个大小为 logn/2 的团，这满足找到一个大小为 Ω(logn) 的团。这也是多项式，因为它在 O(n/logn * n^(log2(3)/3) 时间内运行。抱歉没有早点提供这个！

再会，

我的 AWX 有问题，因为当我配置一个新模板并运行它时，它没有给我任何类型的信息，它保持空白，并且作业说它抛出一个错误。我使用的 AWX 版本是 17.1.0

请帮忙

在此处输入图像描述