پایان نامه کار شناسی با عنوان رنگ آمیزی گراف با الگوریتم ژنتیک

مساله بهینه سازی رنگ آمیزی گراف تعیین حداقل تعداد رنگ های مورد نیاز برای رنگ آمیزی گرافی معین است به گونه ای که هیچ راس مجاوری هم رنگ نباشد و این عدد مورد تظر را عدد

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