المپدیا

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

ابزار کاربر

ابزار سایت


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

شرط جنگل بودن نمایندگان

در گراف $G$ زیر درخت‌های نه لزوما فراگیر $T_1,…,T_k$ مشخص شده‌اند. می‌خواهیم برای هر درخت یک یال به عنوان نماینده‌اش انتخاب کنیم به‌طوری‌که با هم متفاوت باشند و جمعا تشکیل یک جنگل بدهند. ثابت کنید شرط لازم و کافی برای انجام این کار این است که به ازای هر تعدادی از این درخت‌ها مثلا $r$ درخت $T_{i_1},…,T_{i_r}$ داشته باشیم $p\geq q+r$ که $p$ تعداد راس‌ها و $q$ تعداد مولفه‌های همبندی گراف حاصل از $ T_{i_1} \cup … \cup T_{i_r}$ است.

پاسخ


ابزار صفحه