قضیه پنج رنگ

قضیه پنج رنگ نتیجه‌ای است از نظریه گراف که صفحه‌ای به چند منطقه تقسیم شده داده می‌شود. مناطق به گونه‌ای به پنج رنگ مختلف رنگ آمیزی می‌شوند که هیچ دو منطقه مجاوری رنگ یکسان نداشته باشند.
قضیه پنج رنگ از قضیه چهار رنگ می‌رسد اما به طور قابل توجهی اثباتش از آن ساده‌تر است. اثبات این قضیه بر مبنای تلاش شکست خورده‌ای برای اثبات قضیه چهار رنگ توسط آلفرد کمپ در سال ۱۸۷۹ می‌باشد. یازده سال بعد پرسی جان هیوود یک خطا از آن پیدا کرد و بر مبنای کار کمپ قضیه پنج رنگ را اثبات نمود.
نمای کلی اثبات توسط تناقض
در ابتدا یک گراف مسطح G را به نقشه داده شده نسبت می‌دهیم به این صورت که هر منطقه را متناظر با یک راس در نظر می‌گیریم و بین دو راس یال وجود دارد اگر و تنها اگر بین دو منطقه متناظر مرز مشترکی باشد؛ بنابراین حالا مسئله به مسئله رنگ آمیزی گراف تبدیل شده است: رنگ کردن رئوس گراف به طوری که هیچ یالی دو سر همرنگ نداشته باشد.
اثبات بر مشخصه اویلر استوار است تا نشان دهد حتما باید یک راس V وجود داشته باشد که بین حداکثر پنج یال مشترک است و با توجه به این که G مسطح است مثلا می‌تواند در یک صفحه بدون یال‌های متقاطع تعبیه شود.
حال V را از G حذف می‌کنیم. گراف از این کار حاصل می‌شود که یک راس کمتر از G دارد. پس ما می‌توانیم با استقرا فرض کنیم که این را می‌توان با پنج رنگ، رنگ آمیزی کرد. V حتما باید به پنج راس دیگر متصل شود؛ چون در غیر این صورت می‌تواند در گراف G با رنگی که در آن‌ها استفاده نشده است، رنگ آمیزی شود. پس حالا به پنج راس ، ، ، ، نگاه می‌کنیم که در ترتیب دایره‌ای مجاور V هستند (که بستگی به این دارد که چگونه G را نوشته‌ایم). اگر ما همه پنج رنگ را استفاده نکرده باشیم، مسلما می‌توانیم راس V را به رنگی متفاوت از آن‌ها رنگ آمیزی کنیم و گرافی پنج رنگ را تحویل دهیم.
پس ما می‌توانیم فرض کنیم که رئوس به ترتیب رنگ‌های ۱ تا ۵ را گرفته‌اند.
حال زیر گراف از را در نظر می‌گیریم که تنها از رئوسی تشکیل شده که رنگ‌های ۱ و ۳ را دارند و یال‌هایی که دو تا از این رئوس را به هم متصل می‌کند. اگر و در مولفه‌های همبندی متفاوتی از باشند، می‌توانیم رنگ آمیزی مولفه همبندی شامل را معکوس کنیم که بنابراین راس V رنگ ۱ را می‌گیرد و کار تمام است.
اما اگر و در مولفه‌های همبندی یکسانی از بودند، می‌توانیم مسیری در که آن دو را به هم متصل می‌نماید پیدا نماییم که ترتیبی از یال‌ها و رئوس فقط رنگ شده با ۱ و ۳ باشد.
حال زیر گراف از را که در بر گیرنده رئوس رنگ شده با ۲ و ۴ و یال‌های متصل کننده این رئوس به هم است را در نظر می‌گیریم و روندی مشابه قبلی برای آن اجرا می‌کنیم. پس یا می‌توانیم رنگ آمیزی زیر گراف را برعکس نموده و راس V را به رنگ ۲ بزنیم یا از مسیری متشکل از رئوس تنها رنگ شده با ۲ و ۴، و را به هم متصل نماییم. احتمال بعدی به روشنی نامعقول است که مسیری با مسیر ساخته شده در تقاطع داشته باشد؛ بنابراین مخالف با استنباط اولیه G در واقع می‌تواند با پنج رنگ، رنگ آمیزی شود.
الگوریتم پنج رنگ کردن در زمان خطی
در سال ۱۹۹۶، رابرتسون، ساندرز، سیمور و توماس یک الگوریتم چهار رنگ کردن از درجه دوم در «گراف مسطح کارآمد چهار رنگ کردن» خود تعریف کردند. در همان‌جا، آن‌ها مختصرا یک الگوریتم پنج رنگ کردن در زمان خطی تعریف کردند که به طور مجانبی بهینه بود. الگوریتمی که در این جا توصیف شده بر روی چند گراف عمل می‌کند و بر قابلیت داشتن چندین نسخه از یال‌ها بین یک جفت راس تکیه دارد. این قضیه بر اساس قضیه ورنیک می‌باشد که در پایین آمده است:
قضیه ورنیک: فرض می‌کنیم G یک گراف مسطح غیر خالی است که هیچ منطقه‌ای ندارد که با دو یال محدود شده باشد و حداقل درجه پنج دارد. پس G حتما یک راس از درجه پنج دارد که مجاور راسی با درجه حداکثر شش است.
ما نمایشی از این گراف را به کار می‌بریم که در آن هر راس یک لیست پیوندی دایره‌ای از رئوس مجاور را در جهت ساعتگرد گراف مسطح نگه می‌دارد.
در مفهوم، الگوریتم بازگشتی است؛ در هر مرحله گراف را به یک گراف با یک راس کمتر کاهش می‌دهد؛ آن را پنج رنگ می‌کند و سپس از آن رنگ کردن استفاده می‌کند تا معین کند رنگ کردن گراف بزرگتر در زمان ثابتی انجام می‌شود. در عمل بیش از این که برای هر گراف کوچک شده، نمایش یک گراف صریح را نگه داریم، ما رئوس را از گراف حذف می‌کنیم و آن‌ها را به یک پشته اضافه می‌کنیم. سپس در آخر هنگامی که آن‌ها را از پشته خارج می‌کنیم، رنگشان می‌کنیم. ما سه تا پشته را نگه خواهیم داشت:
S 4 : همه رئوس باقی‌مانده با درجه حداکثر چهار یا درجه پنج و حداکثر چهار راس مجاور مجزا (بسته به یال‌ها چندگانه) را در بردارد.
S 5 : همه رئوس باقی‌مانده که درجه پنج، پنج راس مجاور مجزا و حداقل یک راس مجاور با درجه حداکثر شش دارند را در بر می‌گیرد.
S d : همه رئوسی که قبلا از گراف حذف شده‌اند را به ترتیب حذف شدنشان شامل می‌شود.
الگوریتم به نحوه زیر کار می‌کند:
در گام اول، ما همه یال‌های چندگانه را به یال‌های تکی تقلیل می‌دهیم تا گراف ساده شود. سپس ما بر روی رئوس گراف تکرار می‌زنیم تا رئوسی را که با شرایط بیان شده برای S 4 و S 5 مطابقت دارند را در پشته مربوطه قرار دهیم.
سپس تا هنگامی که S 4 خالی نشده است، ما راس v را از S 4 بیرون می‌کشیم و v را از گراف حذف می‌کنیم و آن را به همراه لیستی از همسایگانش در این زمان به S d داخل می‌کنیم. ما هر همسایه قبلی v را بررسی می‌کنیم و در صورت لزوم آن را به S 4 و S 5 وارد می‌کنیم.
هنگامی که S 4 خالی شد، می‌دانیم که گرافمان کمینه درجه پنج را داراست. اگر گراف خالی بود، ما به گام ۵ که در زیر آمده است می‌رویم. در غیر این صورت قضیه ورنیک به ما می‌گوید که S 5 خالی نیست. v را از S 5 بیرون می‌کشیم و آن را از گراف حذف می‌کنیم و v 1 و v 2 و v 3 و v 4 و v 5 را در گراف مسطح به صورت ساعتگرد همسایگان v می‌گذاریم که v 1 همسایه با درجه حداکثر شش است. ما مجاور بودن v 1 و v 3 را بررسی می‌کنیم (این کار با توجه به درجه v 1 در زمان ثابت انجام می‌شود). دو حالت وجود دارد:
اگر v 1 مجاور با v 3 نباشد، ما می‌توانیم این دو راس را به یک تک راس ادغام کنیم. برای انجام این کار ما راس v را از هر دو لیست مجاورت دایره‌ای حذف می‌کنیم. سپس در جایی که v قبلا بود، دو لیست را به هم متصل می‌کنیم. در صورتی که v ارجاعی از موقعیتش در هر لیست را نگه می‌دارد، این کار می‌تواند در زمان ثابت انجام شود. ممکن است faceهایی محدود به دو یال در نقاطی که لیست‌هایشان را ادغام کردیم، به وجود بیاید که ما یک یال از این چنین faceها حذف می‌کنیم. پس از انجام این کار، ما v 3 را به S d وارد می‌کنیم با توجه به این که v 1 راسی است که با آن ادغام شده بود. هر راسی که مورد تاثیر قرار گرفته از ادغام، در زمان مناسب در پشته اضافه شده یا کم می‌شود.
در غیر این صورت v 2 درون منطقه‌ای قرارگرفته که با v و v 1 و v 3 مشخص شده است. در نتیجه v 2 نمی‌تواند مجاور با v 4 که در خارج از این منطقه واقع است. ما v 2 و v 4 را به روشی مشابه با v 1 و v 3 که در بالا آمد ادغام می‌کنیم.
به گام ۲ برو.
در این جا، S 4 و S 5 و گراف خالی شده‌اند. ما رئوس را از S d بیرون می‌کشیم؛ اگر راس با راس دیگری در گام ۳ ادغام شده بود، راسی که با آن ادغام شده بود، پیش‌تر رنگ شده است و ما به آن رنگ مشابه می‌دهیم. این کار مجاز است زیرا ما تنها رئوسی را ادغام کرده بودیم که در گراف اصلی مجاور نبودند. اگر ما آن را در گام ۲ به دلیل این که حداکثر چهار راس مجاور داشته، حذف کرده بودیم، همه همسایگانش در زمان حذف، رنگ شده خواهند بود و ما به سادگی می‌توانیم به آن رنگی که هیچ‌کدام از همسایگانش نگرفته‌اند را بدهیم.
قضیه چهار رنگ
نظریه گراف
رنگ آمیزی گراف