当前位置：文江博客话题详情

恰好具有 k 个颜色边的生成树

发布于 2024-10-06 08:36:37 字数 244 浏览 7 评论 0原文

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

我使用克鲁斯卡尔算法来查找生成树中黑边的最小和最大可能数量。如果 k 超出此范围，则不存在具有 k 个边的生成树。

但我很难思考是否对于该范围内的每个 k 都必须有一棵生成树。我的直觉说是的，它对我尝试过的每个例子都有效，但我不知道如何证明它。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

未央 2024-10-13 08:36:37

令 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 个黑色边缘。

Let G_min = spanning tree with the minimum # of black edges.

Let G_max = spanning tree with the maximum # of black edges.

Let k_min = # of black edges in G_min

Let k_max = # of black edges in G_max

The proof goes as follows. Set G = G_min. Repeat for every black edge in 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.

Step 2 is always possible because there is at least one edge not in G_max in every cycle.

This algorithm maintains the spanning-tree-ness of G as it goes. It adds at most one black edge per step, so G demonstrates a spanning tree with k black edges for all k between k_min and k_max as it goes.

回复收藏 0 原文