0
$\begingroup$

We are considering a connected weighted graph G. 1-tree is a tree with one extra edge added (so it contains exactly one cycle). The task is to find minimum spanning 1-tree of G.
I was thinking of first using any of well-known MST algorithms and then adding an edge of smallest weight to the MST (which is not in the MST). Will something like this work (I am having trouble proving it would)?

$\endgroup$
5
$\begingroup$

I'm not sure this is research level, but here's a sketch. Suppose this algorithm outputs a 1-tree and the actual cheapest 1-tree is some other 1T. Now, since you built your tree with Kruskal's algorithm, you know that the tree directly proceeding adding your last edge(the cycle-inducing edge) was minimal, and as such costs less than any subtree of the "true" cheapest 1-tree.

So, consider the subtree of the "true" 1-tree that is comprised of all edges save one edge in the cycle that your tree doesn't contain(it is easy to show that, unless their cycles are equal, this edge must exist)*. This tree is more expensive than yours. Moreover, since your tree is a tree, adding that edge from the "true" 1T would have made yours a 1-tree. So your final edge must be cheaper than that edge, or you would have chosen that edge. Thus, your 1-tree must be cheapest.

*If the cycles are the same, but the remaining subtrees are different, you are also done since yours was built using Kruskal's algorithm.

$\endgroup$
  • $\begingroup$ Thank you very much Jamie (unfortunately I'm not allowed to upvote your answer yet)! I'd modify your proof a little bit - because G can have more than 1 MST (we didn't assume all weights are distinct), all the strict inequalities should be not strict (for example cost of a subtree of 1T can be equal to cost of T-(last edge)). $\endgroup$ – Harry Jan 10 '11 at 15:02
0
$\begingroup$

Finding the minimum spanning tree can be solved by using the greedy approach that is it looks for the best local optimal solution at a given point of time. Your problem should be extension of the minimum spanning tree. your doubt is that we get two different MST $T_{1}$ and $T_{2}$ of equal weight w. let $e_1$ be the edge with minimum weight $w_{1}$ to be added to form $1-tree_1$ from $T_1 $and $e_2$ be the edge with minimum weight $T_{1}$ to form $1-tree_2$.

Claim:Weights of the $1-tree_{1}$ and $2-tree_{2}$ should be equal.

Let $e_{1},e_{2}..e_{i}$ are the edges that are picked by both $T_{1}$ and T_{2} upto i iterations,

case 1: In this process if there any edge $e_{z}$ with weight $w_{z} < w_{k}$ for any i=1,2..n is not choosen for MST then it means that it would have formed a cycle. so e_{z} will be the edge which would be added to MST to get a 1-tree. so both 1-trees will have same weight

Case 2:if there is no such $e_{z}$ till ith iteration. say at i+1 iteration there make different choice say $e1_{i+1}$ and $e2_{i+1}$. Weights of both of them should be same, otherwise there wont be difference choice. now next edge $e2_{i+1}$ can be added to $T_{1}$ if it does not form as cycle, similarly $e1_{i+1}$ value for $T_{2}$. if they are added then T_{1} and T_{2} remains same till i+2 iteration, if not say addition of e_{i+1} forms a cycle then e2_{i+1} will be e_{z} for T_{1} and e1_{i+1} be the e_{z} for the T_{2}. so both 1-trees have same weight.

Please see whether it is clear.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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