3

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).

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.

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.

Rupert
  • 31
  • 1
  • 2

2 Answers2

6

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.

Keith Randall
  • 22,985
  • 2
  • 35
  • 54
  • there is at least one edge not in G_max, but It's not indeed the new graph is tree. (it can have a cycle or be a disconnected). – Saeed Amiri Dec 06 '10 at 08:33
  • 1
    @Saeed: It can't have a cycle, because step 2 removes an edge from the only cycle. It can't be disconnected because it has the proper number of edges for a tree (algorithm always adds one edge to replace another) and has no cycles. – Rafał Dowgird Dec 06 '10 at 09:20
1

Kruskal's will find you the minimum wight spanning tree - so inorder to find Gmin you need to do this the other way around. gmin = case all the black edged are giving the wight 1 and the white giving the wight 0. the way the algorithm first use all the white edgedes and then the black ones. this way we will get gmin.

shai
  • 11
  • 1