قضیه پنج رنگ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

نمای کلی اثبات توسط تناقض[ویرایش]

در ابتدا یک گراف مسطح 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 در واقع می تواند با پنج رنگ، رنگ آمیزی شود.

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

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

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

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

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

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

  1. در گام اول، ما همه یال های چندگانه را به یال های تکی تقلیل می دهیم تا گراف ساده شود. سپس ما بر روی رئوس گراف تکرار می زنیم تا رئوسی را که با شرایط بیان شده برای S4 و S5 مطابقت دارند را در پشته مربوطه قرار دهیم.
  2. سپس تا هنگامی که S4 خالی نشده است، ما رأس v را از S4 بیرون می کشیم و v را از گراف حذف می کنیم و آن را به همراه لیستی از همسایگانش در این زمان به Sd داخل می کنیم. ما هر همسایه قبلی v را بررسی می کنیم و در صورت لزوم آن را به S4 و S5 وارد می کنیم.
  3. هنگامی که S4 خالی شد، می دانیم که گرافمان کمینه درجه پنج را داراست. اگر گراف خالی بود، ما به گام ٥ که در زیر آمده است می رویم. در غیر این صورت قضیه ورنیک به ما می گوید که S5 خالی نیست. v را از S5 بیرون می کشیم و آن را از گراف حذف می کنیم و v1 و v2 و v3 و v4 و v5 را در گراف مسطح به صورت ساعتگرد همسایگان v می گذاریم که v1 همسایه با درجه حداکثر شش است. ما مجاور بودن v1 و v3 را بررسی می کنیم(این کار با توجه به درجه v1 در زمان ثابت انجام می شود). دو حالت وجود دارد:
    1. اگر v1 مجاور با v3 نباشد، ما می توانیم این دو رأس را به یک تک رأس ادغام کنیم. برای انجام این کار ما رأس v را از هر دو لیست مجاورت دایره ای حذف می کنیم. سپس در جایی که v قبلاً بود، دو لیست را به هم متصل می کنیم. در صورتی که v ارجاعی از موقعیتش در هر لیست را نگه می دارد، این کار می تواند در زمان ثابت انجام شود. ممکن است face هایی محدود به دو یال در نقاطی که لیست هایشان را ادغام کردیم، به وجود بیاید که ما یک یال از این چنین face ها حذف می کنیم. پس از انجام این کار، ما v3 را به Sd وارد می کنیم با توجه به این که v1 رأسی است که با آن ادغام شده بود. هر رأسی که مورد تأثیر قرار گرفته از ادغام، در زمان مناسب در پشته اضافه شده و یا کم می شود.
    2. در غیر این صورت v2 درون منطقه ای قرارگرفته که با v و v1 و v3 مشخص شده است. در نتیجه v2 نمی‌تواند مجاور با v4 که در خارج از این منطقه واقع است. ما v2 و v4 را به روشی مشابه با v1 و v3 که در بالا آمد ادغام می کنیم.
  4. به گام ٢ برو.
  5. در این جا، S4 و S5 و گراف خالی شده اند. ما رئوس را از Sd بیرون می کشیم؛ اگر رأس با رأس دیگری در گام ٣ ادغام شده بود، رأسی که با آن ادغام شده بود، پیش تر رنگ شده است و ما به آن رنگ مشابه می دهیم. این کار مجاز است زیرا ما تنها رئوسی را ادغام کرده بودیم که در گراف اصلی مجاور نبودند. اگر ما آن را در گام ٢ به دلیل این که حداکثر چهار رأس مجاور داشته، حذف کرده بودیم، همه همسایگانش در زمان حذف، رنگ شده خواهند بود و ما به سادگی می توانیم به آن رنگی که هیچ کدام از همسایگانش نگرفته اند را بدهیم.

جستارهای وابسته[ویرایش]

منابع[ویرایش]