生成树k个彩色边缘 [英] spanning tree with exactly k colored edges

问题描述

我有一个连接，无向图边是每个黑色或白色，和一个整数k。 我试着写一个算法，它讲述了一个生成树是否存在恰好有K黑色边缘（并不一定要找到实际的树）。

I have a connected, undirected graph with edges that are each either black or white, and an integer k. I'm trying to write an algorithm that tells whether or not a spanning tree exists with exactly k black edges (doesn't necessarily have to find the actual tree).

我用Kruskal算法找到的最小和黑边尽可能多的生成树。如果k在此范围之外，其中k边缘没有生成树可以存在

I used Kruskal's algorithm to find the minimum and maximum possible number of black edges in a spanning tree. If k is outside this range, no spanning tree with k edges can exist.

但我在遇到麻烦缠绕我的脑海里围绕是否有必要针对该范围内的每k生成树。我的直觉说，是的，它的工作，每例如我试过，但我不能想出如何证明这一点。

But I'm having trouble wrapping my mind around whether there is necessarily a spanning tree for every k within that range. My intuition says yes, and it's worked for every example I've tried, but I can't figure out how to prove it.

有什么建议？先谢谢了。

Any advice? Thanks in advance.

推荐答案

让将G_min =跨越与黑边的最低＃树。

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

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

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

让k_min =在将G_min＃黑边

Let k_min = # of black edges in G_min

让k_max =＃在G_max黑边

Let k_max = # of black edges in G_max

这个证明去如下。设置G =将G_min。在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.

步骤2始终是可能的，因为有至少一个边缘不G_max在每个周期中

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

该算法维护生成树岬的G自有其道理。它增加了每步至多有一个黑边，所以摹展示了一个生成树与k_min和k_max之间所有的k K黑色的边缘，因为它去。

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.

这篇关于生成树k个彩色边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！