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.

My motivation is to find what edges of an weighted, undirected graph are not a part of any 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 - instead of adding the minimum edge from S to T on every step (where S and T being the two sets of vertex) - instead 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 receive 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.

Thanks in advance.

share|improve this question
    
in an unweighted, undirected graph, minimum spanning tree doesn't have meaning. Any spanning tree will do, that is, any acyclic connected subgraph, $(V, E' \subseteq E)$, where the original graph has vertices and edges: $(V,E)$. –  Joe Dec 10 '12 at 23:13
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
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 5 more comments

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

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.