0

This question is very similar to this one: spanning tree with exactly k colored edges

It's not the same question! - As you can see the answer of the question above is not the same (to my Q)....

We have a connected, undirected graph G=(V,E) with edges that are each either red or blue.

We know that |V|=n. We get two numbers: a1,a2āˆˆN where a1 is for the red edges, and a2 is for the blue edges. a1+a2=nāˆ’1.

We have to find an algorithm that checks if there is a spanning tree that have exactly a1 red edges and a2 blue edges. If not, the algorithm returns that there is no spanning tree with this condition.

I tried to get help from the question mentioned above, but I am still stuck. I assume these are very similar questions.

Community
  • 1
  • 1
Yang
  • 1
  • 5
  • But the question is different! Here we have to find an edges with **two** colors that are spanning tree and we have a condition.... Please don't mark as duplicate!! This question don't have the same answer... :-( ā€“ Yang May 20 '15 at 12:28
  • Yes, it does. Read it more carefully and do some algebra. ā€“ David Eisenstat May 20 '15 at 16:37

0 Answers0