-1
$\begingroup$

Is the following a valid algorithm for finding a minimum spanning tree?

Given a weighted graph with unique weights, remove the all edges that are the highest cost edge in any cycle of the original full graph.

Edit: I've changed the description to draw more attention to the differences between this an Kruskal's algorithm (which it is NOT.) Kruskal's algorithm is iterative, this is just a predicate that can be tested on the original unmodified graph.

Improve this question
$\endgroup$
3
  • $\begingroup$ maybe this is a good example of something off topic as being too easy to find on wikipedia ? $\endgroup$
    – Suresh Venkat
    Aug 16, 2010 at 22:44
  • $\begingroup$ I agree to Suresh. $\endgroup$
    – ilyaraz
    Aug 16, 2010 at 22:44
  • $\begingroup$ @ilyaraz: I've looked into this some before and never seen the characterization you referenced in your answer. $\endgroup$
    – BCS
    Aug 17, 2010 at 5:17

2 Answers 2

Reset to default
2
$\begingroup$

Indeed, it is correct. You can characterize MST as a tree such that every edge outside it is a maximum edge in the corresponding cycle. The proof is an easy excersise.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Do you have a reference to such a characterization? -- I think you are correct, but I'm not 100% sure that that shows that the edges in the MSP can't be a minimum edge in any cycle. $\endgroup$
    – BCS
    Aug 17, 2010 at 5:14
  • 1
    $\begingroup$ @BCS: I think you mean you're not sure that that shows that the edges in the MST can't be a maximum edge in any cycle, right? Consider any cycle in the original graph, with maximum edge length between u and v, and suppose that there is an MST containing uv. Deleting that edge gives a graph with a u-containing component and a v-containing component. Now convince yourself that there must be at least 2 edges on the original cycle that span these 2 components: we already know there must be at least 1 (the edge we just deleted), and if you trace around the cycle you must... $\endgroup$
    – user651
    Aug 27, 2010 at 7:26
  • 1
    $\begingroup$ ...come back to the component you started from at least once. So, there are at least 2 spanning edges, and adding either one will reconnect the graph. Adding back any of the non-uv (= non-max-length) edges will produce a connected graph with shorter length than we started with, hence the original graph could not have been a MST. (Proof by contradiction.) $\endgroup$
    – user651
    Aug 27, 2010 at 7:30
2
$\begingroup$

This is not a well-defined algorithm. You can tweak it to make it well-defined, by changing the description to

Remove all edges, from high to low weight, that do not make the graph disconnected.

and this is equivalent to kruskal's algorithm.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This algo is not iterative. Kruskal's is. This algo only looks at the origonal graph. Kruskal's looks at the graph after edges have been removed. This algo is not Kruskal's. $\endgroup$
    – BCS
    Aug 17, 2010 at 5:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.