ارایه یک الگوریتم تقریبی حریصانه برای رنگ آمیزی گراف ها

مسئله رنگ آمیزی گراف ( GCP ) یک مسئله بهینه سازی ترکیباتی است و مشخص کردن عدد رنگی G (x) یک مسئله یNP-hard است زیرا همانطور که تعداد رئوس و یال ها در گراف افزایش می یابد پیچیدگی مسئله نیز افزایش می یابد چون هر الگوریتم عدد رنگی نمونه را نمی تواند پیدا کند و زمان اجرای هر الگوریتم برای هر نمونه می تواند متفاوت باشد و به همین دلیل الگوریتم های تقریبی بسیاری ارائه شده است که از نظر زمان اجرا و جواب برای گراف های معیار واقع در کتابخانهdimacs با هم مقایسه شده اند. مسئله رنگ آمیزی گراف کاربردهای زیادی در میدان های متفاوتی مانند حل مسائل بیولوژیکی، ارتباطات و اینترنت دارد و همچنین برای کاربردهای مهندسی و مسائل واقعی جهان استفاده می شود. به دلیل اهمیت به دست آوردن جواب های بهتر برای مسئله رنگ آمیزی گراف تعداد الگوریتم هایی که جواب تقریبی می دهند مانند الگوریتم های ابتکاری، فراابتکاری و حریصانه افزایش یافت. هدف ما ارائه یک الگوریتم تقریبی برای رنگ آمیزی گراف می باشد که جواب ها را بهبود دهد و زمان اجرا را کاهش دهد و برای نشان دادن بهبود این الگوریتم، آن را در نرم افزار متلب پیاده سازی و بر روی نمونه هایی از گراف های معیار اجرا می کنیم و کارآیی الگوریتم خودمان را با بهترین الگوریتم های موجود مقایسه می کنیم.

کلیدواژه ها:

عددرنگی ، الگوریتم های حریصانه رنگ آمیزی ، درجه ی راس.