problems related to theory of computation!!

[shruti_vip]

1. Prove that for any fixed set of node locations, the minimum possible total length of a tree interconnecting all nodes is less than the minimum possible length of any ring interconnecting all nodes.


As it is maths subject GRE forum, I think that I can get help from u guys.


-Waiting for your help...
Thanx in advance,
Shruti

[Mike_L]

Suppose L is the minimum possible length of any ring interconnecting all nodes.

Remove any one path from this ring that connects two nodes and which does not go through any other node. Call the length of the removed path R.

Then you are left with a tree of total length L-R which interconnects all nodes. Let M be the minimum possible total length of a tree interconnecting all nodes. Then M <= L-R < L.

qed

[Pensive]

I think Mike is right.
It's not a difficult problem.