Сравнительный анализ алгоритмов раскраски обыкновенного взвешенного графа

Рассматриваются и сравниваются алгоритмы решения задачи поиска «минимаксной» раскраски взвешенного по вершинам графа. Приведена математическая постановка задачи, указаны критерии оптимальности решения. Описан точный алгоритм, всегда находящий минимальные по количеству цветов раскраски методом Магу и затем отыскивающий среди них «минимаксный» вариант с помощью 3 модификаций алгоритма «критического пути». Описаны три быстрых эвристических алгоритма: алгоритм, работающий с упорядоченным по локальным степеням списком вершин; алгоритм, основанный на удалении вершин и смежных рёбер; алгоритм, использующий степень насыщения вершин. Все алгоритмы рассмотрены с примерами. Для оценки эффективности алгоритмов поставлен вычислительный эксперимент на нескольких сотнях случайно сгенерированных графов. Алгоритмы сравнивались по скорости работы и близости результата к «минимаксному» варианту раскраски.