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

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

تعریف: به افراز راسی V1,,Vn از گراف G یک پوشش درختی می‌گوییم هرگاه زیرگراف القایی روی هر Vi برای هر 1in یک درخت باشد. عدد درختی G که با a(G) نمایش داده می‌شود کوچکترین عدد طبیعی k است که برای گراف G یک پوشش درختی V1,,Vn داشته باشیم. ثابت کنید:

a(G)1+max(δ(G)/2 که در این نامساوری ماکسیمم روی همه‌ی زیرگراف‌های القایی G از G گرفته می‌شود.


ابزار صفحه