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

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