قضیه پنج رنگ

قضیه پنج رنگ نتیجه‌ای است از نظریه گراف که صفحه‌ای به چند منطقه تقسیم شده داده می‌شود. مناطق به گونه‌ای به پنج رنگ مختلف رنگ آمیزی می‌شوند که هیچ دو منطقه مجاوری رنگ یکسان نداشته باشند. قضیه پنج رنگ از قضیه چهار رنگ می‌رسد اما به طور قابل توجهی اثباتش از آن ساده‌تر است. اثبات این قضیه بر مبنای تلاش شکست خورده‌ای برای اثبات قضیه چهار رنگ توسط آلفرد کمپ در سال ۱۸۷۹ می‌باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر مبنای کار کمپ قضیه پنج رنگ را اثبات نمود.

نمای کلی اثبات توسط تناقض

در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می‌دهیم به این صورت که هر منطقه را متناظر با یک رأس در نظر می‌گیریم و بین دو رأس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد. اثبات بر مشخصه اویلر استوار است تا نشان دهد حتماً باید یک رأس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلاً می‌تواند در یک صفحه بدون یال‌های متقاطع تعبیه شود. حال V را از G حذف می‌کنیم. گراف از این کار حاصل می‌شود که یک رأس کمتر از G دارد. پس ما می‌توانیم با استقرا فرض کنیم که این را می‌توان با پنج رنگ، رنگ آمیزی کرد. V حتماً باید به پنج رأس دیگر متصل شود؛ چون در غیر این صورت می‌تواند در گراف G با رنگی که در آن‌ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج رأس $V_{1}$، $V_{2}$، $V_{3}$، $V_{4}$، $V_{5}$ نگاه می‌کنیم که در ترتیب دایره‌ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته‌ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلماً می‌توانیم رأس V را به رنگی متفاوت از آن‌ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم. پس ما می‌توانیم فرض کنیم که رئوس به ترتیب رنگ‌های ۱ تا ۵ را گرفته‌اند. حال زیر گراف $G_{13}$ از $G'$ را در نظر می‌گیریم که تنها از رئوسی تشکیل شده که رنگ‌های ۱ و ۳ را دارند و یال‌هایی که دو تا از این رئوس را به هم متصل می‌کند. اگر $V_{1}$ و $V_{3}$ در مؤلفه‌های همبندی متفاوتی از $G_{13}$ باشند، می‌توانیم رنگ آمیزی مؤلفه همبندی شامل $V_{1}$ را معکوس کنیم که بنابراین رأس V رنگ ۱ را می‌گیرد و کار تمام است. اما اگر $V_{1}$ و $V_{3}$ در مؤلفه‌های همبندی یکسانی از $G_{13}$ بودند، می‌توانیم مسیری در $G_{13}$ که آن دو را به هم متصل می‌نماید پیدا نماییم که ترتیبی از یال‌ها و رئوس فقط رنگ شده با ۱ و ۳ باشد. حال زیر گراف $G_{24}$ از $G'$ را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال‌های متصل کننده این رئوس به هم است را در نظر می‌گیریم و روندی مشابه قبلی برای آن اجرا می‌کنیم. پس یا می‌توانیم رنگ آمیزی زیر گراف $G_{24}$ را برعکس نموده و رأس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، $V_{2}$ و $V_{4}$ را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در $G_{13}$ تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می‌تواند با پنج رنگ، رنگ آمیزی شود.

الگوریتم پنج رنگ کردن در زمان خطی

در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان‌جا، آن‌ها مختصراً یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می‌کند و بر قابلیت داشتن چندین نسخه از یال‌ها بین یک جفت رأس تکیه دارد. این قضیه بر اساس قضیه ورنیک می‌باشد که در پایین آمده است:

قضیه ورنیک: فرض می‌کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه‌ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتماً یک رأس از درجه پنج دارد که مجاور رأسی با درجه حداکثر شش است.

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

• S₄: همه رئوس باقی‌مانده با درجه حداکثر چهار یا درجه پنج و حداکثر چهار رأس مجاور مجزا (بسته به یال‌ها چندگانه) را در بردارد.
• S₅: همه رئوس باقی‌مانده که درجه پنج، پنج رأس مجاور مجزا و حداقل یک رأس مجاور با درجه حداکثر شش دارند را در بر می‌گیرد.
• S_d: همه رئوسی که قبلاً از گراف حذف شده‌اند را به ترتیب حذف شدنشان شامل می‌شود.

الگوریتم به نحوه زیر کار می‌کند:

1. در گام اول، ما همه یال‌های چندگانه را به یال‌های تکی تقلیل می‌دهیم تا گراف ساده شود. سپس ما بر روی رئوس گراف تکرار می‌زنیم تا رئوسی را که با شرایط بیان شده برای S₄ و S₅ مطابقت دارند را در پشته مربوطه قرار دهیم.
2. سپس تا هنگامی که S₄ خالی نشده است، ما رأس v را از S₄ بیرون می‌کشیم و v را از گراف حذف می‌کنیم و آن را به همراه لیستی از همسایگانش در این زمان به S_d داخل می‌کنیم. ما هر همسایه قبلی v را بررسی می‌کنیم و در صورت لزوم آن را به S₄ و S₅ وارد می‌کنیم.
3. هنگامی که S₄ خالی شد، می‌دانیم که گرافمان کمینه درجه پنج را داراست. اگر گراف خالی بود، ما به گام ۵ که در زیر آمده است می‌رویم. در غیر این صورت قضیه ورنیک به ما می‌گوید که S₅ خالی نیست. v را از S₅ بیرون می‌کشیم و آن را از گراف حذف می‌کنیم و v₁ و v₂ و v₃ و v₄ و v₅ را در گراف مسطح به صورت ساعتگرد همسایگان v می‌گذاریم که v₁ همسایه با درجه حداکثر شش است. ما مجاور بودن v₁ و v₃ را بررسی می‌کنیم (این کار با توجه به درجه v₁ در زمان ثابت انجام می‌شود). دو حالت وجود دارد:
   1. اگر v₁ مجاور با v₃ نباشد، ما می‌توانیم این دو رأس را به یک تک رأس ادغام کنیم. برای انجام این کار ما رأس v را از هر دو لیست مجاورت دایره‌ای حذف می‌کنیم. سپس در جایی که v قبلاً بود، دو لیست را به هم متصل می‌کنیم. در صورتی که v ارجاعی از موقعیتش در هر لیست را نگه می‌دارد، این کار می‌تواند در زمان ثابت انجام شود. ممکن است faceهایی محدود به دو یال در نقاطی که لیست هایشان را ادغام کردیم، به وجود بیاید که ما یک یال از این چنین faceها حذف می‌کنیم. پس از انجام این کار، ما v₃ را به S_d وارد می‌کنیم با توجه به این که v₁ رأسی است که با آن ادغام شده بود. هر رأسی که مورد تأثیر قرار گرفته از ادغام، در زمان مناسب در پشته اضافه شده یا کم می‌شود.
   2. در غیر این صورت v₂ درون منطقه‌ای قرارگرفته که با v و v₁ و v₃ مشخص شده است. در نتیجه v₂ نمی‌تواند مجاور با v₄ که در خارج از این منطقه واقع است. ما v₂ و v₄ را به روشی مشابه با v₁ و v₃ که در بالا آمد ادغام می‌کنیم.
4. به گام ۲ برو.
5. در این جا، S₄ و S₅ و گراف خالی شده‌اند. ما رئوس را از S_d بیرون می‌کشیم؛ اگر رأس با رأس دیگری در گام ۳ ادغام شده بود، رأسی که با آن ادغام شده بود، پیش تر رنگ شده است و ما به آن رنگ مشابه می‌دهیم. این کار مجاز است زیرا ما تنها رئوسی را ادغام کرده بودیم که در گراف اصلی مجاور نبودند. اگر ما آن را در گام ۲ به دلیل این که حداکثر چهار رأس مجاور داشته، حذف کرده بودیم، همه همسایگانش در زمان حذف، رنگ شده خواهند بود و ما به سادگی می‌توانیم به آن رنگی که هیچ‌کدام از همسایگانش نگرفته‌اند را بدهیم.

جستارهای وابسته

• قضیه چهار رنگ
• نظریه گراف
• رنگ آمیزی گراف

منابع

• ویکی‌پدیای انگلیسی قضیه پنج رنگ