生成树,正好是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个黑色边缘.