Задача раскраски взвешенного графа возникает в том случае, когда в вершинах графа необходимо выполнить некоторые работы различной целочисленной длительности, причём в смежных вершинах работы не могут выполняться одновременно. <...> Хорошим примером этой задачи может служить проблема распределения команд в многопроцессорной системе, когда требуется минимизировать загрузку каждого процессора. <...> Имеется неориентированный связный взвешенный граф = ( , ), где — множество вершин, — множество рёбер, ( ) — вес -й вершины. <...> Необходимо раскрасить вершины графа таким образом, чтобы никакие две смежные вершины не были окрашены в один цвет, и при этом максимальная сумма весов вершин одного цвета стремилась к минимуму: max min, (1 ) где — подмножество несмежных вершин графа, окрашенных в -й цвет. <...> Точный (здесь и далее — без кавычек, тем не менее, этот алгоритм нельзя назвать полностью «точным», т. к. третий этап решения содержит эвристический метод) алгоритм [3] поиска раскраски минимального веса можно разделить на три этапа. <...> На первом этапе решается задача поиска всех максимально внутренне устойчивых подмножеств графа где — число вершин в этом подмножестве. <...> 1 4 , № 2 ( 7 7 ) T V e T e l l C Cl a m C l l T e А a m - A W a m А А А А А А А А А А А i m m А торых равна хроматическому числу, а элементами являются максимально внутренне устойчивые подмножества, охватывающие все вершины (т. е. их объединение даёт множество этапах используется метод Магу [4]. <...> На этих раз ( — число кортежей , а ) решается задача распределения программ по однородным вычислительным системам. <...> Матрица загрузки приборов (процессоров) формируется следующим образом: строки соответствуют вершинам графа, столбцы — цветам раскраски. <...> Если вершина является элементом кортежа пересечении ( й строки и номера, под которым стоит в кортеже не могла быть назначена другому цвету. <...> На третьем этапе используется <...>