مهدی رضایی نژاد - دانشجوی کارشناسی ارشد نرم افزار-دانشگاه آزاد اسلامی واحد اراک- گروه کا
سید عبدالمجید موسوی - استادیار و عضو هیئت علمی دانشگاه لرستان
مجید رحیمی نسب - استادیار و عضو هیئت علمی دانشگاه لرستان

مساله رنگ آمیزی گراف عبارت است از انتصاب K رنگ به رئوس یک گراف به صورتی که هیچ دو راس مجاور در گراف دارای رنگ یکسانی نباشند. کمترین تعداد رنگی که بتوان با آن یک گراف را رنگ آمیزی کرد ، عدد رنگی گراف نامیده می شود. یافتن عدد رنگی در مساله رنگ آمیزی گراف از جمله مسائل NP-COMPLETE می باشد لذا می توان از الگوریتم های تقریبی برای حل این مساله استفاده کرد. در این مقاله می خواهیم با استفاده از الگوریتم فرااکتشافی جستجوی هارمونی ، این مساله را حل کنیم. نتایچ به دست آمده از اجرای روش پیشنهادی روی گراف های تست DIMACS نشان دهنده کارایی بهتر این روش نسبت به الکوریتم های مورد مقایسه می باشد.

مساله رنگ آمیزی گراف ، NP-COMPLETE ، گراف ، الگوریتم های فرا اکتشافی ، الگوریتم جستجوی هارمونی