Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.

share|improve this question
2  
I think the question is probably meant to be more conceptual and less algorithmic. Here's a hint: What if I gave you a graph with $n$ edges (that is, a spanning tree with one edge that doesn't belong in it). How would you know which is the edge that doesn't belong? –  Joe Dec 10 '12 at 23:19
    
Thanks Joe, I obviously meant a weighted graph (fixed that). About your hint: for example a graph with 3 vertex and 3 edges, fully connected with every edge weighing 2. Every edge is in at least one MST. –  The-Q Dec 11 '12 at 5:46
    
Every edge having the same weight is the same as unweighted, for MST purposes. Why don't you focus on the (non-degenerate) case where every edge has distinct weights? Even in some standard MST algorithms, the edge weights are assumed to be distinct (although if weights are the same, you can break ties, e.g. lexographically) –  Joe Dec 11 '12 at 5:56
1  
How is the question exactly phrased. I was expecting something like "the unique maximal edge is not in any MST" as an answer. –  A.Schulz Dec 11 '12 at 7:31
1  
This sounds like one of those questions that only make sense if you know what the questioner is thinking. If the question was "what is a case where an edge can never be part of a MST", I can think of a good answer. (Hint: Think of a triangle.) –  usul Dec 11 '12 at 7:51
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.