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

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

solving the graph sum colouring problem using a heuristic algorithm

graph sum colouring is the assignment of natural numbers to the vertices of a simple graph so that the sum of the numbers assigned to the vertices of the graph is minimized. its most important application is in the scheduling problems. given that this is one of the np-hard problems, no exact solution has been provided so far. therefore, in this study, a hybrid heuristic, based on the idea of identifying independent sets of graph vertices and assigning the smallest natural number available for the largest independent set has been developed. the proposed algorithm is tested on graphs in well-known libraries of randomly generated graphs. the results show the efficiency of the proposed algorithm.