Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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


ابزار صفحه