Processing math: 60%

المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

  1. فرض کنید ‎G=FH‎. ثابت کنید χ(G)χ(F)χ(H).
  2. فرض کنیم ‎D‎ یک سودهی از ‎G‎ باشد و ‎χ(G)>rs‎. فرض کنید هر ‎vV(D)‎ به یک عدد حقیق ‎f(v)‎ تخصیص داده شده است. ثابت کنید ‎D‎ دارای یک مسیر ‎u0ur‎ با ‎f(u_0) \leq‎ ... ‎\leq f(u_r)‎ و یا یک مسیر ‎v_0 \rightarrow \cdots \rightarrow v_s‎ با ‎f(v_0) > \cdots > f(v_s)‎ است. ‎
  3. با استفاده از قسمت قبل ثابت کنید که هر دنباله از ‎rs+1‎ عدد حقیقی متمایز دارای یک زیردنباله افزایشی به اندازه ‎r+1‎ و یا یک زیردنباله کاهشی به اندازه ‎s+1‎ است. ‎

ابزار صفحه