الگوریتم مبتنی بر خوشه بندی سلسله مراتبی برای رنگ امیزی گراف ها

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

Keywords:

رنگ امیزی گراف , خوشه بند , داده کاوی