رنگ آمیزی آزمند

معمولاً الگوریتم رنگ آمیزی آزمند، بدترین عملکرد خود را بر روی گراف‌های کامل دوبخشی k _n,n دارد که یال نظیر رئوس x_i و x_j که i=j حذف شده‌اند.

در صورتی‌که پس از شماره‌گذاری رئوس، دو راسی که در یک یال حذف شده قرار دارند به صورت متوالی شماره‌گذاری شوند، چنین گرافی با n رنگ، رنگ آمیزی می‌شود درحالیکه یک گراف ۲-رنگ پذیر است؛ بنابراین ترتیب رئوس در الگوریتم آزمند اهمیت فراوانی دارد.

یکی از روش‌های معمول شماره‌گذاری رئوس، انتساب کمترین اولویت به راس با کمترین درجه و مرتب‌سازی بقیه رئوس به همین شکل است. اگر هر زیرگراف یک گراف دارای بیشینه درجه d باشد الگوریتم حریصانه حداکثر از d+۱ رنگ استفاده می‌کند.

برای گرافی با بیشینه درجه D الگوریتم حریصانه از حداکثر D+۱ رنگ استفاده می‌کند. قضیه بروک نشان می‌دهد این تعداد با دو استثنا (گراف‌های cliques, odd cycle) حداکثر برابر D است. یکی از روش‌های اثبات این نظریه، شماره‌گذاری رئوس به صورتیست که دو راس اول، مجاور راس نهایی بوده ولی با یکدیگر مجاور نباشند بنابراین تعداد رنگ‌های استفاده شده الگوریتم آزمند برابر D خواهد بود. پاسخ به این سؤال که آیا برای گراف مفروض G وعدد مفروض K یک الگوریتم آزمند وجود دارد که گراف را با کمتر از K رنگ، رنگ آمیزی کند یا خیر یک مسئله NP-Complete است.

تعدادی از معروف‌ترین الگوریتم‌های شماره‌گذاری رئوس عبارتند از:

ترتیب خاص از پیش تعیین شده (SPECIFIC-PREDEFINED-ORDERING:SP)

ترتیب کاهش درجه نودها (DECREASING DEGREE ORDERING: DD) به عبارت دیگر هر بار راس رنگ نشده با بزرگترین درجه

ترتیب افزایش درجه نودها(INCREASING DEGREE ORDERING: ID) به عبارت دیگر هر بار راس رنگ نشده با کوچکترین درجه

ترتیب درجه اشباع نودها (SATURATION DEGREE ORDERING:SD) که درجه اشباع یک نود عبارتست از تعداد رنگ‌های به کار رفته در رنگ آمیزی نودهای مجاورش

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

از معروف‌ترین الگوریتم‌های حریصانه مرتب‌سازی رنگ‌ها عبارتند از:

SIMPLE-SEARCH-GREEDY:SSG: این روش کلاس‌های رنگ را بر اساس یک ترتیب از پیش تعریف شده انتخاب می‌کند.

LARGEST-FIRST-SEARCH-GREEDY:LFSG: کلاس‌های رنگ را بر اساس سایزشان (تعداد نودهای موجود در هر یک) به ترتیب نزولی مرتب کرده از بینشان انتخاب می‌کند؛ بنابراین، این روش متمایل به ایجاد کلاس‌های رنگ با بزرگترین سایز است.

SMALLEST-FIRST-SEARCH-GREEDY:SFSG: کلاس‌های رنگ را بر اساس سایز آن‌ها به ترتیب صعودی مرتب می‌کند؛ بنابراین این روش متمایل به تراز کردن و توزیع یکنواخت نودها در بین کلاس‌های رنگ می‌باشد.

هر یک از متدهای مرتب‌سازی آزمند رنگ‌ها در ترکیب با روش‌های مختلف مرتب‌سازی نودها، یک الگوریتم کامل آزمند برای رنگ آمیزی گراف ایجاد می‌کنند که نتیجه هر الگوریتم می‌تواند متفاوت باشد.

گراف G را کاملاً ترتیب پذیر می‌گوییم اگر ترتیب π وجود داشته باشد به صورتی‌که با اعمال این ترتیب بر روی هر زیرگراف از گراف مفروض، الگوریتم آزمند و الگوریتم بهینه رنگ آمیزی، یکسان عمل کنند. به وسیلهٔ این ترتیب هیچ چهار راس aوbوcوd وجود ندارد که اگر در یک مسیر قرار داشته باشند راس a قبل از راس b و نیز راس c بعد از راس d قرار بگیرد. گراف‌های کاملاً ترتیب پذیر زیرمجموعه‌ای از گراف‌های کامل هستند اما تشخیص چنین گرافی یک مسئله ان‌پی-کامل می‌باشد.

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

نمونه‌ای از شبه کد رنگ آمیزی آزمند:

• پیاده‌سازی با جاوا

• ویکی‌پدیا انگلیسی، [۱]
• ارائه یک مدل مبتنی بر رنگ آمیزی گراف برای تنظیم جداول زمانبندی دروس دانشگاهی، مریم معصومی، دکتر سید امیرحسن منجمی، دکتر ناصر نعمت بخش، دانشگاه اصفهان، دانشکده فنی، گروه کامپیوتر
• داده ساختارها و مبانی الگوریتم‌ها، دکتر محمد قدسی