المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۶

  1. فرض کنید ‎$G = F \cup H$‎. ثابت کنید $\chi(G) \leq \chi(F)\chi(H)$.
  2. فرض کنیم ‎$D$‎ یک سودهی از ‎$G$‎ باشد و ‎$\chi(G) > rs$‎. فرض کنید هر ‎$v \in V(D)$‎ به یک عدد حقیق ‎$f(v)$‎ تخصیص داده شده است. ثابت کنید ‎$D$‎ دارای یک مسیر ‎$u_0 \rightarrow \cdots \rightarrow u_r$‎ با ‎$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$‎ است. ‎

ابزار صفحه