چکیده

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

کلیدواژه ها:

رنگ آمیزی جمعی گراف

مجموعه مستقل رئوس گراف

الگوریتم فراابتکاری

نویسندگان:

مرتضی رجب زاده^*1، امین محمدنژاد²، کوروش عشقی³

¹استادیار، دانشکده مهندسی، مرکز آموزش عالی محلات، محلات، ایران.

²محقق، دانشکده مهندسی، مرکز آموزش عالی محلات، محلات، ایران.

³استاد، دانشکده مهندسی صنایع، دانشگاه صنعتی شریف، تهران، ایران.

DOR:

دانلود فایل مقاله                    منابع                   XML