رنگ‌آمیزی جدول

روش رنگ آمیزی جدول، روشی است که با آن می‌توان برخی مسائل، در رابطه با صفحات $m*n$ را حل نمود .

ابتدا به توضیح این روش می پردازیم :

1- ابتدا یک الگوریتم ارائه می‌کنیم که خانه‌های جدول، 2 یا چند رنگ، رنگ آمیزی کند .

2- سپس با استفاده از این رنگ آمیزی، حکم را ثابت می‌کنیم .

نکته

رنگ‌آمیزی جدول معمولاً برای اثبات عدم توانای انجام کاری استفاده می‌شود

چند نمونه

مثال اول ) یک فیل در یک صفحهٔ شطرنجی 8×9 قرار دارد، در هر حرکت میتواند از یک خانه با شمارهٔ (x,y) یکی از خانه‌ها $(x-1,y-1)(x-1,y+1)(x+1,y-1)(x+1,y+1)$ آیا فیل میتواند از خانهٔ (0و0)به (1و0) برود ؟

حل ) صفحهٔ شطرنج را شطرنجی سیاه و سفید می‌کنیم .

در هر حرکت از یک خانهٔ سیاه به یک سیاه دیگر میرویم و چون مقصد سفید است هرگز به آن نمی‌توانیم برویم .

مثال دوم ) یک صفحه مشبک $2k*2k$ موجود است، به قسمی که خانه‌های گوشه‌ای متقابل آن حذف شده‌اند(خانهٔ (1,1) و (2k , 2k)). تعدادی دومینو در دست می‌باشد. آیا می‌توان صفحه فوق را به‌طور کامل با دومینوها پوشاند. (یعنی یک پوشش کامل را بوسیله دومینوها داشته باشیم).

حل)این کار نشدنی است.

صفحهٔ شطرنج را شطرنجی سیاه و سفید می‌کنیم . هر دومینو یک خانه سیاه و یک خانه سفید را می‌پوشاند. بنابراین تعداد خانه‌های سیاه و خانه‌های سفید باید برابر باشد، . اما صفحه مسئله ما تعداد بیشتری خانه سیاه نسبت به سفید دارد. چون هر دو خانهٔ حذف شده سفید است. پس نمی‌توان آن را با دومینوها پوشاند.

روش کلی

اکثر مسائلی که با روش رنگ آمیزی جدول حل می‌شوند به این صورت هستند و در اکثر موارد ما بعد از ارائه یک الگوریتم رنگ آمیزی باید یک کمیت تعریف کرده و مقدار اولیه آن را به دست آوریم، سپس تغییرات این کمیت در هر مرحله حساب کرده و به این نتیجه برسیم که رسیدن به حالت نهایی برای کمیت فرضی خلاف حکم امکان است پس پذیر نمی‌باشد .

برای اطلاعات بیشتر

http://daneshnameh.roshd.ir/mavara/mavara-index.php?page=رنگ+آمیزی+و+همخوانیI&SSOReturnPage=Check&Rand=0

http://www.njavan.com/forum/showthread.php?p=68062

منابع

کتاب زرد تر کیبیات (انتشارات فاطمی)