المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

پوشش دوبخشی گراف ‎$G$‎، مجموعه‌ای از زیرگراف‌های دوبخشی آن است که هر یال از ‎$G$‎ حداقل در یکی از آن‌ها آمده باشد. وزن این پوشش برابر با مجموع تعداد رئوس این زیرگراف‌ها است. فرض کنید ‎$bc(G)$‎ کوچکترین عددی باشد که یک پوشش دوبخشی از ‎$G$‎ با آن وزن موجود باشد.

  1. ثابت کنید ‎$bc(K_{2^n})\leq 2^n.n$
  2. ثابت کنید ‎$bc(K_{2^n})\geq 2^n.n$

یادآوری: برای این بخش شاید مجبور به استفاده از نابرابری حسابی-هندسی شوید. طبق این نامساوی برای اعداد مثبت ‎$a_1,\ldots,a_n$‎ داریم: ‎\begin{equation*}‎ ‎\frac{\sum_{i=1}^n a_i}{n} \geq \sqrt[n]{\Pi_{i=1}^n a_i}‎ ‎\end{equation*}‎


ابزار صفحه