algorithm - 具有恰好 k 个彩色边的生成树

Question

我有一个连接的无向图，其边都是黑色或白色，还有一个整数 k。我正在尝试编写一个算法来判断是否存在具有恰好 k 个黑色边缘的生成树（不一定要找到实际的树）。

我使用 Kruskal 算法在生成树中找到最小和最大可能的黑边数。如果 k 超出此范围，则不存在具有 k 条边的生成树。

但是我很难考虑是否必须为该范围内的每个 k 生成一棵生成树。我的直觉说是的，并且它适用于我尝试过的每个示例，但我不知道如何证明它。

有什么建议吗？提前致谢。

Answer 1

令 G_min = 黑色边数最少的生成树。

让 G_max = 黑色边数最大的生成树。

让 k_min = G_min 中的黑边数

让 k_max = G_max 中的黑色边数

证明如下。设置 G = G_min。对 G_max 中的每个黑边重复：

  1) If the edge is already in G, do nothing.
  2) If the edge is not in G, add it to G and remove another edge
     from the cycle thus induced in G.  Remove one not in G_max.

步骤 2 总是可能的，因为在每个循环中至少有一个边缘不在 G_max 中。

该算法在运行过程中保持 G 的生成树性。它每一步最多添加一个黑色边，因此 G 演示了一个生成树，其中 k_min 和 k_max 之间的所有 k 都有 k 个黑色边。

Answer 2

Kruskal's 会为您找到最小 wight 生成树 - 因此，为了找到 Gmin，您需要以相反的方式执行此操作。gmin = case 所有黑边都给 wight 1，白色给 wight 0。算法首先使用所有白色边缘然后是黑色边缘的方式。这样我们就会得到gmin。