问题标签 [independent-set]

我创建了一个测试图来尝试从中创建一个独立的集合。我知道独立集是一组未连接的顶点，但我不确定如何在合金 4.2 中实现这一点。这是我所拥有的：

我在 SQL Server 中有我的数据表AC，其结构为：

我必须计算给定Conditional Probability的年度AuthorIDCoAuthorID

P(AuthorID|CoAuthorID)=P(AuthorID ∩ CoAuthorID) / P(CoAuthorID)

而在2005交叉口操作的年份。

最初，例如，AuthorID = 677and CoAuthorID = 901706，Year = 2005我试过这个：

对于P(AuthorID)：

它返回390所以P(AuthorID)=1/390

对于P(CoAuthorID)：

它返回1所以P(CoAuthorID)=1/1

对于P(AuthorID ∩ CoAuthorID)：

它返回 1 行：

而数据中有 3 行，这意味着AuthorID并CoAuthorID在数据中共存 3 次，2005这意味着这两位作者在 2005 年共同贡献了 3 次。所以，

1. 应该是什么价值P(AuthorID ∩ CoAuthorID)？应该是1还是1/3？
2. 其他计算也正确吗？

谢谢！

线路覆盖、分支覆盖和独立路径覆盖有什么区别？

给定以下场景，路径会是什么样子？

以下链接上的控制流程图图片 --> http://testerstories.com/files/Path.Test.011.png

非常感谢为每个人找到真正路径的步骤。

谢谢 ：）

我正在尝试实现一个 Prolog 谓词，该谓词获取二叉树（表示为 t(Left, Root, Right)）并返回一个列表，该列表是该树的最大独立集（MIS）及其大小。我首先了解到 MIS(T) 是有根的 MIS 和没有根的 MIS 之间的最大值。然后，我使用了两个定理，说明有根的MIS是所有子树的没有根的MIS的统一，而没有根的MIS是所有子树的MIS的统一。

它确实成功地检索了一组最大大小，但它不会继续搜索相同大小的其他 MIS。提前感谢您的帮助！

我开发了一种算法，可以根据距离约束找到图的最小独立支配集。（我使用 Python 和 NetworkX 来生成图表并获取对）

该算法使用蛮力方法：

• 找到所有可能的边对
• 检查哪些节点满足距离约束
• 找出所有可能的独立支配集
• 比较找到的独立支配集并找到最小支配集

对于少量节点，它不会有所作为，但对于大量节点，程序真的很慢。

有什么方法可以让我使用不同的方法让它运行得更快吗？

谢谢

关于拟阵中电路的唯一性，请参考这篇笔记： http: //math.mit.edu/~goemans/18433S13/matroid-notes.pdf。在定理 4.1 的证明中，最后 2 句“由于 S 也是独立的，我们必须有 |X| = |S| 并且因为 e ∈ C1 - f，我们必须有 X = S + e - f ∈ I . 但这意味着 C2 ⊆ S + e - f = X 这是一个矛盾，因为 C2 是依赖的。”。谁能解释一下为什么“|S| = |X|” 为什么“e ∈ C1 - f，我们必须有 X = S + e - f ∈ I。”？几个小时以来我都不知道它是怎么回事..

我正在学习如何使用分支和减少方法找出最大独立集问题的时间复杂度。以下是抄自教科书的计算。

在这里，我无法找出红色框标记的行是如何来自它的前一行的。在上一行中，为什么求和部分中没有 i 下标？ 这背后的原因是什么？

我在想每个子树有两种情况：根在独立集中，根不在集中。如何编写递归算法来查找树中独立集的数量？这棵树是 n 元的。

https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

到目前为止，这是我的解决方案，但它不正确。如果当前子树的父节点已经包含在独立集中，则变量 parentIncluded 等于 true，因此当前子树的根不能添加到独立集中。如果 parentIncluded 等于 false，则可以将当前子树的根添加到独立集中。当 parentIncluded 为 false 时，有两种情况。第一种情况：将根添加到集合中。第二种情况：不添加根。

所以我正在练习一些编程面试问题，并偶然发现了这个示例 pdf，它建议“了解如何使用掩码并以独立于机器的方式创建它们”。但它没有详细说明机器依赖和机器独立掩码之间的区别。

我通常只是找出提供我想要的掩码的整数，例如，如果我只想要最后 4 位，我会这样做：

我不明白为什么这将取决于机器，如果是的话。

那么创建与机器无关的掩码的示例是什么？什么是创建依赖于机器的掩码的示例？

也许他们在谈论的是，如果您需要一个不是整数的掩码，在这种情况下我的方法将不起作用（除了整数之外，我从来不需要掩码）？

我读到完美图的最大独立集可以在多项式时间内找到。

是否有任何多项式时间算法可以找到完美图的所有独立集的列表？