问题标签 [independent-set]

我从这里（第 8、9 页）阅读了关于 NP 硬度的信息，在注释中，作者将 3-SAT 形式的问题简化为可用于解决最大独立集问题的图形。

在示例中，作者将以下 3-SAT 问题转换为图。3-SAT问题是：

生成的等效图是：

作者指出，两个节点通过一条边连接，如果：

1. 它们对应于同一子句中的文字
2. 它们对应于一个变量及其倒数。

我很难理解作者是如何提出这些规则的。

• 为什么我们需要在变量和它的逆变量之间画边？
• 假设有两个子句，子句 1 有 (a,b,~c)，子句 2 有 (~a,b,c) 来连接子句 1 和子句 2，为什么我们必须连接 a 和 ~a？为什么我们不能将 a (clause 1) 与 c (clause 2) 连接起来呢？

我编写了一个版本的高斯消除来验证一组二进制向量的线性独立性。它输入一个矩阵 (mxn) 来评估并返回：

• True（线性无关）：未找到零行。
• False（线性相关）：如果最后一行为零。

它似乎总是运行良好，或者至少几乎运行良好。我发现当矩阵在最后一行有两个重复向量时它不起作用：

该函数说矩阵是“线性独立的”，因为没有找到零行，而且结果中确实有任何零行。但是调试我发现在某些时候一行变成了零，但是在一些行操作之后它又恢复了“正常”。

我仔细检查了代码，使其工作的唯一方法是在流程结束之前找到“零行”时也返回“false” ，更准确地说，在行操作期间：

我想知道这是否正确，或者我只是在“修补”错误的代码。

谢谢！

下面是完整的代码：

我想确认数据是 iid。我正在调查每小时降水数据。所附数据是一个区域内 7 个仪表的 q99，根据定义它们应该是 iid（我每天最多取一个值）。

我正在使用“extremes”包中的“extremalindex”，但结果很奇怪并且显示的值非常低，而它应该接近1。数据称为group_c，代码是

谁能帮我？？？我的代码有什么问题。

我选择阈值 0 是因为所有数据都应包含在进一步分析中（数据为 Q99）

请在此处找到使用的数据

仪表年月日小时雨量_in_mm

假设我们有一个无向图 G = (V,E)，并且我们构造一个新的图 G'，如果两个节点在 G 中有一个共同的邻居节点，则它们是相邻的。如果我们有这样的一个，有人可以解释为什么以下陈述是正确的建筑 G'?

如果 G 有一个大小为 n 的独立集合，则 G' 有一个大小为 n 的匹配。如果 G' 有一个大小为 n 的匹配，则 G 有一个大小为 n 的独立集合。

不幸的是，我不知道这个问题

我的任务是检查图形着色中使用的最少颜色数量，这只是图形的色数。我的无向图是 2 正则的（每个顶点都是 2 度）。我找到了解决方案

（最大独立集数）/顶点数=颜色数（色数）

https://imgur.com/a/ZtyP4v9 - 它的样子

如您所见，如果结果为 2，则可以是 2 色，如果结果大于 2，则可以是 3 色。

但我不知道如何在这样的图中找到最大独立集。

我有一个图像名称列表和一个（阈值）相似度矩阵。相似关系是自反和对称的，但不一定是传递性的，即如果image_i与image_j和相似image_k，则不一定意味着image_j和image_k相似。

例如：

相似度矩阵sm解释如下：如果sm[i, j] == 1那么image_i和image_j相似，否则它们不相似。在这里，我们看到与和image_0相似，但与不相似（这只是非传递性的一个例子）。image_1image_2image_1image_2

sm我想保留最大数量的唯一图像（根据给定的矩阵，这些图像都是成对不相似的）。对于此示例，它将是[image_2, image_3, image_4]or [image_1, image_2, image_3]（通常有多个这样的子集，但我不介意保留哪个子集，只要它们具有最大长度）。我正在寻找一种有效的方法来做到这一点，因为我有成千上万的图像。

编辑：我原来的解决方案如下

但是，不能保证它会返回一个最大长度的子集。考虑以下示例：

此解决方案将返回['image_1', 'image_4']，而所需的结果是['image_0', 'image_2', 'image_4']or ['image_1', 'image_2', 'image_4']。

更新：请参阅我的答案，该答案使用图论更详细地解释了该问题。我仍然愿意接受建议，因为我还没有找到一种相当快速的方法来获得数千张图像列表的结果。

我有点困惑。我知道如何将 3-SAT 减少到 IS。将 3-SAT 转换为 IS 图的示例是创建一个表示 3-SAT 的每个子句的图，然后将 x 和 !x 连接起来，然后将其提交给 IS。我们如何将其应用于更通用的 SAT <=p IS 减少，而不将 SAT 减少到 3-SAT？对我来说，这似乎是相同的方式，但我有一种感觉并非如此，我错过了一些东西。SAT的一个例子：

我们是否会以同样的方式对其进行转换，是否有一个通用的步骤序列可用于所有 SAT 实例？我将如何证明？

一个简单的贪心算法来找到一个最大的独立集，我认为这将花费 O(n) 时间，因为不会访问超过两次的顶点。为什么wiki说需要O（m）时间？

我有 2 个问题。

编号。1：我有一个运行了 1 年（热身期之后）的模拟模型，它模拟了患者进入诊所接受治疗（每天设置）（患者可能每周来接受一次治疗，下一次周一 5 周）。可以将其视为日常模拟终止。

我对独立和相同分布(IID) 的第一个问题是我需要比较诊所中的患者数量（比如说，星期一）。然而，每个星期一的患者数量可能从星期一到星期一不同（这个星期一，我们有 100 名病人；下星期一我们有 105 名病人；下星期一我们有 97 名病人）。每一天都相互独立，但是，我不相信每一天（在本例中为星期一）都是相同分布的（考虑到n不同）。因此，问题是：我如何比较不同分布的统计独立天数？

编号。2：安排患者首次就诊 60 分钟（60 分钟窗口）。即使医生、护士、药剂师（以及所有工作人员）对提供给患者的时间有自己的分配（因此，IID），我面临的另一个问题是每个患者都有不同的需求：（例如）

患者 A：医生和护士。

患者B：医生护士和药剂师。

患者 C：医生和护士以及社会工作者。

因此，即使患者有 60 分钟的预约时间，因为有不同的工作人员与患者互动，在这种情况下，患者就诊的持续时间是 IID 吗？他们是独立的（患者之间没有联系）；他们应该是相同的分布，因为他们（患者和工作人员）只有 60 分钟可供使用，但是，我对此不确定。

在数据集不是 IID 的情况下，如何比较它们？

非常感谢任何帮助和指导。

我有一个很难开始的家庭作业问题。我们正在研究 Karp（单次调用）减少以显示难处理性。对于这个任务，这个问题是故意模糊的。我希望这里的某个人可能知道它或者可以提供一个解决方案示例来帮助我入门。

该问题仅在他们提供的代码中进行了描述。它具有以下组件：

B = (G, T, k) 其中 B 是“Blah”问题的一个实例，G = (V,E) 是图（未加权，无向），T 是 V 中的顶点子集，k 是整数。B 的证书返回 G 的子图 S = (V', E')。还提供了 yes 实例的验证器：

一个是的例子如果

我看到这个问题与独立集或顶点覆盖问题之间有一些相似之处。我觉得这些是很好的候选者，可以减少以显示难以处理，但对问题的理解还不够好。如果在某处讨论这个问题，或者任何人都可以提供一些例子，我将不胜感激。谢谢！