المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۴

تعریف: به افراز راسی $V_1, \cdots, V_n$ از گراف $G$ یک پوشش درختی می‌گوییم هرگاه زیرگراف القایی روی هر $V_i$ برای هر $1\leq i \leq n$ یک درخت باشد. عدد درختی $G$ که با $a(G)$ نمایش داده می‌شود کوچکترین عدد طبیعی $k$ است که برای گراف $G$ یک پوشش درختی $V_1, \cdots, V_n$ داشته باشیم. ثابت کنید:

$$ a(G) \leq 1 + \lfloor max(\delta(G')/2 \rfloor$$ که در این نامساوری ماکسیمم روی همه‌ی زیرگراف‌های القایی $G'$ از $G$ گرفته می‌شود.


ابزار صفحه