المپدیا

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

ابزار کاربر

ابزار سایت


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

سوال ۵

فرض کنید گراف $G$ با $n$ راس داده شده است. همچنین می‌دانیم که $G$ یک گراف ۳-رنگ‌پذیر است. الگوریتمی چند جمله‌ای ارائه کنید که راس‌های $G$ را با حداکثر $3\sqrt{n}$ رنگ رنگ‌آمیزی کند.(راهنمایی: مجموعه‌ی $N(v)$، یعنی مجموعه‌ی همسایه‌های راس $v$ را در نظر بگیرید).


ابزار صفحه