المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

  1. یک گراف هم‌بند ساده‌ی ‎$G$‎ داریم. به ازای هر زیرگراف القایی ‎$H$‎ از ‎$G$‎، داریم: $\kappa'(H) \le 10$‎. بیشینه و کمینه‌ی ‎$\chi(G)$‎ را بیابید.
  2. فرض کنید ‎$n$‎ و ‎$\Delta$‎ اعدادی طبیعی باشند. ثابت کنید شرط لازم و کافی برای آن که عدد رنگی یالی هر گراف ساده‌ی ‎$n$ رأسی و ‎ $m$ ‎یالی با درجه‌ی بیشینه‌ی ‎$\Delta$‎، برابر ‎$\Delta+1$‎ باشد، آن است که $‎\frac{(n-1)\Delta}{2} < m \le \frac{n\Delta}{2}$‎ و ‎$n$‎ فرد باشد.

ابزار صفحه