المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۵:الگوریتم ها:سوال ۲

بازگشت اقلیدس

گراف کامل، وزن‌دار و اقلیدسی (وزن یال‌های هر مثلث در نامساوی مثلثی صدق می‌کنند!) $G$ داده شده است. وزن راس $v$ در گراف $H$ برابر مجموع وزن یال‌های مجاور راس $v$ در $H$ می‌باشد. هدف یافتن $H$ (زیرگراف فراگیر و هم‌بندی از $G$) است که بیشینه‌ی وزن رئوسش کمینه باشد.

با فرض این‌که بزرگ‌ترین یال درخت فراگیر کمینه‌ی $G$، $\alpha$ باشد، الگوریتمی چند جمله‌ای ارائه دهید که زیر گرافی فراگیر و هم‌بند از $G$ بیابد که بیشینه‌ی وزن رئوسش حداکثر $5 \alpha$ باشد.


ابزار صفحه