You are given an undirected connected graph with an even number of edges. Half of the edges have weight less than C (possibly with repetitions), and the other half of edges all have weight C. Is it true that every MST of the graph includes the same number of edges of weight C? If Yes, describe an efficient algorithm for finding the number of edges of weight C in every MST of the graph. The output is between 0 and |E| / 2, no need to return the MST. If No, show a counterexample.
My work so far – I’ve managed to prove to myself that the number of C weighing edges included in a spanning tree (not minimum) can be anywhere between 0 and |E| / 2 (using a cycle with C edges crossing it). Obviously, I couldn’t find a counterexample yet. It feels like what’s preventing me from creating two different MST’s with a different number of C edges is that for creating a graph that has more than one MST you need to have cycles, and if a C edge is contained in the cycle it won’t be chosen (Kruskal). That is the direction I’m leaning towards for a proof, proving a more general claim obviously. Assuming the above is in fact true, I need to show an efficient algorithm for finding the number of C edges in every MST. The question states there is no need to return an MST, so it seems like there should be a better algorithm than finding the MST and counting the number of C edges in it, meaning this algorithm should be more efficient than sorting. From what I showed above, it could be anywhere between 0 and |E| / 2 so I’m kinda lost here too.
Asked By : Ben Danon
Answered By : Hendrik Jan
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/41169 Ask a Question Download Related Notes/Documents
