小编Rup*_*ert的帖子

我有一个连通的,无向图,边缘分别为黑色或白色,以及整数k.我正在尝试编写一种算法,该算法可以判断生成树是否存在k个黑色边缘(不一定要找到实际的树).

我使用Kruskal的算法来查找生成树中最小和最大可能的黑边数.如果k超出此范围,则不存在具有k个边的生成树.

但是我无法理解是否必须为该范围内的每个k生成一棵生成树.我的直觉是肯定的,它对我尝试过的每个例子都有效,但我无法弄清楚如何证明它.

有什么建议？提前致谢.