我有一个连通的无向图，其边为黑色或白色，并且有一个整数 k。
我正在尝试编写一个算法来判断是否存在具有正好 k 个黑边的生成树（不一定必须找到实际的树）。
我使用克鲁斯卡尔算法来查找生成树中黑边的最小和最大可能数量。如果 k 超出此范围，则不存在具有 k 个边的生成树。
但我很难思考是否对于该范围内的每个 k 都必须有一棵生成树。我的直觉说是的，它对我尝试过的每个例子都有效，但我不知道如何证明它。
有什么建议吗？提前致谢。
令 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 个黑色边缘。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
