حل مسأله رنگ آمیزی گراف با استفاده از اتاماتای یادگیر سلولی

مسأله رنگ آمیزی رئوس گراف عبارت است از انتساب یک رنگ به هر یک از رئوس گراف؛ بگونه ای که به هر دو رأس مجاور دلخواه از گراف، رنگ های متفاوتی اختصاص داده شود. مسأله رنگ آمیزی گراف از مسائل بغرنج می باشد و به همین دلیل الگوریتمهای متعددی که جوابهای قابل قبول در زمان کوتاه تولید می کنند، برای حل آن گزارش شده است. در این مقاله با استفاده از اتاماتای یادگیر سلولی نامنظم، الگوریتمی برای حل این مسأله ارایه شده است. الگوریتم پیشنهادی، با الگوریتمهای کارامیا، فانابیکی و مالاگوتی مقایسه شده است. طبق نتایج بدست آمده بر روی گرافهای نمونه، مشاهده می گرددکه الگوریتم پیشنهادی نتایج به مراتب بهتری در زمانی قابل قبول را تولید می کند.

Keywords:

مساله رنگآمیزی گراف , الگوریتمهای اکتشافی , اتاماتای یادگیر سلولی