دور همیلتونی اقلیدسی

از shaazzz
پرش به ناوبری پرش به جستجو

یه گراف کامل وزن دار داریم که راسهاش مجموعه ای از نقاط روی صفحه اند و وزن هر یال فاصله اقلیدسی راس هایش است. اگر مجموع وزن یالهای زیر درخت فراگیر با کمترین مجموع وزن بین همه ی زیر درخت های فراگیر را T و مجموع وزن یالهای دور همیلتونی با کمترین مجموع وزن بین همه ی دور های همیلتونی را C بگیریم. ثابت کنید C حداکثر 2T است.از این که یال ها در نابرابری مثلث صدق میکنن استفاده کنین.