4

给定一个具有红色和蓝色边的图G和一个常数K ，设计一个确定性的线性时间算法，该算法找到G的生成树，其中恰好有K个红色边（False如果这样的生成树不存在，则返回）。

到目前为止我们做了什么：

让每条红色边的权重为 -1，每条蓝色边的权重为 0。

找到最小生成树（使用标准线性时间算法）。因此，我们有一个权重最小的生成树T，这意味着我们使用了尽可能多的红色边，因为红色边只会降低权重。

如果T中有少于K个红色边，我们返回。False

如果正好有K个红色边，我们就完成了，T就是答案。

如果有超过K个红色边缘，我们需要将它们替换为蓝色边缘。

这是我们的问题，我们如何在线性时间内做到这一点？

添加的每个蓝色边缘都会创建一个循环，因此从循环中删除一个红色边缘将起作用，但我们如何才能以这种方式实现线性？这甚至是一个好方法吗？

4

1 回答 1

3

提示

您可以使用两次Prim 算法在线性时间内完成此操作。（通常 Prim 的算法不是线性时间，但是当你只有两种类型的边时，你不需要花时间对边进行排序）。

通过 1

在第一遍中，在红色边缘之前跟随蓝色边缘，并标记您被迫采用的任何红色边缘。

如果在此过程中标记 C 条边，那么我们知道在任何生成树解中必须至少有 C 条红色边，因此如果 C>K，则不可能。

通过 2

假设我们在第一遍中找到了 C ( < K ) 标记的边。

在第二遍中，在蓝色之前跟随红色边缘，直到额外红色边缘的总数达到 KC。在第二遍中，您还可以遵循第一遍中标记的红色边缘（这些不计入您的总数）。

如果您的额外红边没有达到 KC，那么这是不可能的。

于 2014-02-11T16:27:42.307 回答