المپدیا

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

ابزار کاربر

ابزار سایت


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

مجموعه‌ی تعیین‌کننده

گراف $G$ و یک رنگ‌آمیزی معتبر راسی با $K(G)$ رنگ برای آن داده شده است. یک مجموعه‌ي تعیین‌کننده یک زیر مجموعه از راس‌های گراف است به طوری که با ثابت نگه داشتن رنگ این راس‌ها، بقیه‌ی راس‌ها دارای رنگ‌آمیزی یکتای معتبری با $x$ رنگ بشوند. فرض کنید تمام مجموعه‌های تعیین کننده‌ی مینمال برای این رنگ‌آمیزی داده شده، $x-1$ راس داشته باشند. ثابت کنید در همسایگی هر راس از $G$، تمام رنگ‌ها به استثنای رنگ خود راس آمده است.

پاسخ


ابزار صفحه