Vestnik of Don State Technical University Vestnik of Don State Technical University Вестник Донского государственного технического университета 1992-5980 2699 10.12737/4546 Инженерное дело, технологии и технические науки Engineering, Technology and Technical Sciences Инженерное дело, технологии и технические науки Comparative analysis of coloring algorithms for ordinary weighted graph Сравнительный анализ алгоритмов раскраски обыкновенного взвешенного графа Мерзленко Андрей Сергеевич Merzlenko Andrey Сергеевич corruptGoverment@mail.ru Кобак Валерий Григорьевич Kobak Valeriy Григорьевич valera33305@mail.ru 06 06 2014 06 06 2014 14 2 https://naukaru.ru/en/nauka/article/2699/view

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

Algorithms of solving the “minimax” weighted graph coloring problem are considered and compared. The mathematical formulation of the problem is presented; the solution optimality criteria are stated. The exact algorithm that always finds the minimum count of colors through Maghout method and then finds the “minimax” option using 3 versions of the critical path method is described. Three fast heuristic algorithms are described: the algorithm that works with the list of vertexes arranged by the local degrees; the algorithm based on the removal of the points and adjacent edges; the algorithm using the vertex saturation rate. All algorithms are considered with examples. To evaluate the algorithm efficiency, a computational experiment on several hundred of randomly generated graphs is set up. The algorithms were compared by the operating speed and the proximity of the result to the "minimax" version of coloring.

 взвешенные графы раскраска взвешенного графа теория расписаний. weighted graphs weighted graph coloring scheduling theory.

УДК 681.3-181.48Сравнительный анализ алгоритмов раскраски обыкновенного взвешенного графа[1] А. С. Мерзленко, В. Г. Кобак  Рассматриваются и сравниваются алгоритмы решения задачи поиска «минимаксной» раскраски взвешенного по вершинам графа. Приведена математическая постановка задачи, указаны критерии оптимальности решения. Описан точный алгоритм, всегда находящий минимальные по количеству цветов раскраски методом Магу и затем отыскивающий среди них «минимаксный» вариант с помощью 3-х модификаций алгоритма «критического пути». Описаны три быстрых эвристических алгоритма: алгоритм, работающий с упорядоченным по локальным степеням списком вершин; алгоритм, основанный на удалении вершин и смежных ребер; алгоритм, использующий степень насыщения вершин. Все алгоритмы рассмотрены с примерами. Для оценки эффективности алгоритмов поставлен вычислительный эксперимент на нескольких сотнях случайно сгенерированных графов. Алгоритмы сравнивались по скорости работы и близости результата к «минимаксному» варианту раскраски.Ключевые слова: взвешенные графы, раскраска взвешенного графа, теория расписаний. Введение. Задача раскраски взвешенного графа возникает в том случае, когда в вершинах графа необходимо  выполнить некоторые работы различной целочисленной длительности, причём в смежных вершинах работы не могут выполняться одновременно. Хорошим примером этой задачи может служить [1] Работа выполнена в рамках инициативной НИР

Карп, Р. М. Сводимость комбинаторных проблем / Р. М. Карп // Кибернетический сборник, вып. 12. - Москва : Мир, 1975, с. 1638. Karp, R. М. Svodimost kombinatornykh problem. [Reducibility of combinatorial problems.] Kiberneticheskiy sbornik, iss. 12. Moscow: Mir, 1975, pp. 1638 (in Russian). Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон.  Москва : Мир, 1982.  416 с. Garey, М., Johnson, D. Vychislitelnyye mashiny i trudnoreshayemyye zadachi. [Computers and Intractibility.] Moscow: Mir, 1982, 416 p. (in Russian). Кобак, В. Г. Алгоритм раскраски взвешенного графа / В. В. Букин, В. Г. Кобак // Известия СКНЦ ВШ. Технические науки. - 1998. - №2. Kobak, V.G., Bukin, V.V. Algoritm raskraski vzveshennogo grafa. [Algorithm of weighted graph coloring.] Izvestiya SKNTs VSh. Tekhnicheskiye nauki. 1998, no. 2 (in Russian). Кофман, А. Введение в прикладную комбинаторику / А. Кофман.  Москва : Наука, 1975.  480 с. Kauffman, А. Vvedeniye v prikladnuyu kombinatoriku. [Introduction to applied combinatorics.] Moscow: Nauka, 1975, 480 p. (in Russian). Кобак, В. Г. Модификация алгоритма обслуживания «по критическому пути» для систем с избирательными свойствами приборов / В. Г. Кобак // Микропроцессорные и цифровые системы.  2003.  № 2(6).  С. 156-162. Kobak, V.G. Modifikatsiya algoritma obsluzhivaniya «po kriticheskomu puti» dlya sistem s izbiratelnymi svoystvami priborov. [Operation algorithm modification “through the critical path” for systems with specific equipment properties.] Mikroprotsessornyye i tsifrovyye sistemy, 2003, no. 2(6), pp. 156-162 (in Russian). Курейчик, В. М. Теория и практика эволюционного моделирования / В. В. Емельянов, В. М. Курейчик, В. В. Курейчик.  Москва : ФИЗМАТЛИТ, 2003.  432 с. Kureychik, V.M., yemelyanov, V.V., Kureychik, V.V. Teoriya i praktika evolyutsionnogo modelirovaniya. [Theory and practice of evolutionary modeling.] Moscow: FIZMATLIT, 2003, 432 p. (in Russian). Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес.  Москва : Мир, 1988.  432 с. Christofides, N. Teoriya grafov. Algoritmicheskiy podkhod. [Graph theory. An algorithmic approach.] Moscow: Mir, 1988, 432 p. (in Russian). Койнов, Р. В. Практикум по дискретной математике / Р. В. Койнов, Л. С. Лисицына.  Санкт-Петербург : Издательство СПбГУ ИТМО, 2004.  78 с. Koynov, R.V., Lisitsyna, L.S. Praktikum po diskretnoy matematike. [Workshop on discrete mathematics.] Saint Petersburg: Izdatelstvo SPbGU ITMO, 2004, 78 p. (in Russian). Евстигнеев, В. А. Применение теории графов в программировании / В. А. Евстигнеев.  Москва : Наука, 1985.  352 с. Yevstigneyev, V.A. Primeneniye teorii grafov v programmirovanii. [Application of graph theory in programming.] Moscow: Nauka, 1985, 352 p. (in Russian). 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.  С. 8586. Welsh, D. J. A., Powell, M.B. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 1967, no. 10(1), pp. 8586.