Рассматриваются и сравниваются алгоритмы решения задачи поиска «минимаксной» раскраски взвешенного по вершинам графа. Приведена математическая постановка задачи, указаны критерии оптимальности решения. Описан точный алгоритм, всегда находящий минимальные по количеству цветов раскраски методом Магу и затем отыскивающий среди них «минимаксный» вариант с помощью 3-х модификаций алгоритма «критического пути». Описаны три быстрых эвристических алгоритма: алгоритм, работающий с упорядоченным по локальным степеням списком вершин; алгоритм, основанный на удалении вершин и смежных ребер; алгоритм, использующий степень насыщения вершин. Все алгоритмы рассмотрены с примерами. Для оценки эффективности алгоритмов поставлен вычислительный эксперимент на нескольких сотнях случайно сгенерированных графов. Алгоритмы сравнивались по скорости работы и близости результата к «минимаксному» варианту раскраски.
взвешенные графы, раскраска взвешенного графа, теория расписаний.
УДК 681.3-181.48
Сравнительный анализ алгоритмов раскраски обыкновенного взвешенного графа[1]
А. С. Мерзленко, В. Г. Кобак
Рассматриваются и сравниваются алгоритмы решения задачи поиска «минимаксной» раскраски взвешенного по вершинам графа. Приведена математическая постановка задачи, указаны критерии оптимальности решения. Описан точный алгоритм, всегда находящий минимальные по количеству цветов раскраски методом Магу и затем отыскивающий среди них «минимаксный» вариант с помощью 3-х модификаций алгоритма «критического пути». Описаны три быстрых эвристических алгоритма: алгоритм, работающий с упорядоченным по локальным степеням списком вершин; алгоритм, основанный на удалении вершин и смежных ребер; алгоритм, использующий степень насыщения вершин. Все алгоритмы рассмотрены с примерами. Для оценки эффективности алгоритмов поставлен вычислительный эксперимент на нескольких сотнях случайно сгенерированных графов. Алгоритмы сравнивались по скорости работы и близости результата к «минимаксному» варианту раскраски.
Ключевые слова: взвешенные графы, раскраска взвешенного графа, теория расписаний.
Введение. Задача раскраски взвешенного графа возникает в том случае, когда в вершинах графа необходимо выполнить некоторые работы различной целочисленной длительности, причём в смежных вершинах работы не могут выполняться одновременно. Хорошим примером этой задачи может служить
1. Карп, Р. М. Сводимость комбинаторных проблем / Р. М. Карп // Кибернетический сборник, вып. 12. - Москва : Мир, 1975, с. 1638.
2. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. Москва : Мир, 1982. 416 с.
3. Кобак, В. Г. Алгоритм раскраски взвешенного графа / В. В. Букин, В. Г. Кобак // Известия СКНЦ ВШ. Технические науки. - 1998. - №2.
4. Кофман, А. Введение в прикладную комбинаторику / А. Кофман. Москва : Наука, 1975. 480 с.
5. Кобак, В. Г. Модификация алгоритма обслуживания «по критическому пути» для систем с избирательными свойствами приборов / В. Г. Кобак // Микропроцессорные и цифровые системы. 2003. № 2(6). С. 156-162.
6. Курейчик, В. М. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик. Москва : ФИЗМАТЛИТ, 2003. 432 с.
7. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес. Москва : Мир, 1988. 432 с.
8. Койнов, Р. В. Практикум по дискретной математике / Р. В. Койнов, Л. С. Лисицына. Санкт-Петербург : Издательство СПбГУ ИТМО, 2004. 78 с.
9. Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев. Москва : Наука, 1985. 352 с.
10. Welsh, D. J. A. An upper bound for the chromatic number of a graph and its application to timetabling problems / D. J. A. Welsh, M. B. Powell // The Computer Journal №10(1), 1967. С. 8586.
