Аннотация на русском языке: Анализ эвристических методов и описание вычислительных экспериментов с помощью программы для эвристической оценки хроматического числа. Рассмотрены такие методы как жадный алгоритм, метод полного перебора, метод случайного перебора, а также метод перебора с ограничением в глубину. Проведены эксперименты, целью которых является оценка качества решений, формируемых различными методами. Сравнение результатов, даваемых различными методами для графов, различающихся такими свойствами как, например, число вершин и плотность связей, в зависимости от параметров поиска конкретных методик, дает данные для анализа актуальности использования этих методов для решения конкретных практических задач, таких как составление расписаний, кластерный анализ, вычисление производных, распараллеливание численных методов, распределение частот, цифровые знаки, распределение регистров процессора.

The summary in English: Аnalysis of heuristic methods and description of computational experiments using a program for heuristic estimation of chromatic number. Such methods as greedy algorithm, full search method, random search method, as well as the method of search with depth restriction are considered. Experiments have been carried out to assess the quality of solutions formed by different methods. Comparison of the results given by different methods for graphs with different properties such as, for example, the number of vertices and density of connections, depending on the search parameters of specific techniques, gives data for the analysis of the relevance of using these methods for solving specific practical problems, such as scheduling, cluster analysis, calculation of derivatives, parallelization of numerical methods, frequency distribution, digital signs, distribution of processor registers.

Ключевые слова: вершина, граф, хроматическое число, алгоритмы, эвристические методы, раскраска графа, эксперимент, плотность, выборка.
Key words: vertex, graph, chromatic number, algorithms, heuristic methods, graph coloring, experiment, density, sampling