OVERVIEW OF GRAPH COLORING METHODS AND ALGORITHMS

The problem of graph coloring using heuristic methods was considered. The purpose of the work is to analyze heuristic methods and describe computational experiments using a program for heuristic evaluation of a chromatic number. Such methods as the greedy algorithm, the full-search method, the random-search method, and the depth-limited search method were considered. Experiments aimed at evaluating the quality of the solutions formed by different methods were conducted. Comparison of the results of the use of different methods for graphs which differ in such properties as, for example, the number of vertices and connection density, depending on search parameters of specific methods, gives us data for the analysis of the relevance of the use of these methods for the solution of specific practical problems, such as scheduling, cluster analysis, calculation of derivatives, parallelization of numerical methods, frequency distribution, digital signs, allocation of processor registers. __________ ОГЛЯД МЕТОДІВ ТА АЛГОРИТМІВ РОЗФАРБОВУВАННЯ ГРАФУ В роботі розглядається задача пошуку хроматичного числа евристичними методами. Ціллю даної роботи є аналіз евристичних методів та опис обчислювальних експериментів за допомогою програми для евристичної оцінки хроматичного числа. Розглянуто такі методи як жадібний алгоритм, метод повного перебору, метод випадкового перебору, а також, метод перебору з обмеженням в глибину. Проведено експерименти, з метою оцінки якості рішень, які сформовані за допомогою різних методів.