Go Back   TestMagic Forums > Test preparation > GRE Subject Tests > GRE Subject Test: Mathematics
Register FAQForum Rules Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
Old 09-06-2005, 06:48 PM   #1 (permalink)
shruti_vip
Eager!
 
Join Date: Jan 2004
Posts: 35
shruti_vip just joined TestMagic.
problems related to theory of computation!!

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
shruti_vip is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 10-02-2005, 05:28 AM   #2 (permalink)
Mike_L
Trying to make mom and pop proud
 
Join Date: Aug 2005
Posts: 6
Mike_L just joined TestMagic.
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
Mike_L is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 10-15-2005, 09:04 AM   #3 (permalink)
Pensive
Trying to make mom and pop proud
 
Join Date: Aug 2005
Posts: 5
Pensive just joined TestMagic.
I think Mike is right.
It's not a difficult problem.
Pensive is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

What you can do
You cannot post new threads
You cannot post replies
You cannot post attachments
You cannot edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On



All times are GMT. The time now is 03:16 AM.

Contact TestMagic   TestMagic Forums      Archive   

TestMagic Locations   Legal   Privacy


Content Relevant URLs by vBSEO 3.0.0
Copyright © 1998-2008 TestMagic
Ad Management by RedTyger

Scroll Up