Processing math: 84%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۲

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

ابزار صفحه