生成树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屋!