ناشناس
سوال 10842
فرض کنید G یک گراف کامل وزندار باشد که وزن های آن در نامساوی مثلثی صدق میکنند یعنی به ازای هر x,y,z عضو V داریم: w(xy)+w(yz) بزرگ تر مساوی w(xz) است. نشان دهید که اگر T یک درخت بهینه درG باشد،آنگاه وزن هر دور بهینه در G حداکثر 2w(T) خواهد بود؟
ثبت پاسخ جدید
برای ثبت پاسخ، لطفا وارد حساب کاربری خود شوید.
پاسخ‌ها
0 پاسخهنوز پاسخی ثبت نشده است.