-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.

$\endgroup$

closed as off topic by Suresh Venkat, txwikinger, Sylvain Peyronnet, Jukka Suomela, Aryabhata Aug 16 '10 at 22:54

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ maybe this is a good example of something off topic as being too easy to find on wikipedia ? $\endgroup$ – Suresh Venkat Aug 16 '10 at 22:44
  • $\begingroup$ I agree to Suresh. $\endgroup$ – ilyaraz Aug 16 '10 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 '10 at 5:17
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.

$\endgroup$
  • $\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 '10 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 '10 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 '10 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.

$\endgroup$
  • $\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 '10 at 5:10

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