В неорграфе G(A,U) взвесим вершины, т.е. каждой вершине сопоставим целое число, и потребуем при этом, чтобы смежным вершинам были сопоставлены разные числа. Если число трактовать как номер краски, то такое взвешивание вершин называют раскраской графа. Раскраска графа, в которой используется минимальное число красок, называется минимальной. Число красок минимальной раскраски является одной из характеристик графа и называется хроматическим числом. К задаче определения минимальной раскраски графа сводятся многие задачи.

Алгоритм раскраски А.П.Ершова

Введем понятие расстояния между вершинами как длину минимального пути между ними. Назовем 1-окрестностью вершины множество вершин на расстоянии единицы от , p-окрестностью вершины а- множество вершин на расстоянии от .

Выберем вершину и присвоим ей первую краску Выберем из 2-окрестности этой вершины любую вершину и присвоим ей ту же краску. Объединим эти две вершины в одну так, что все ребра, связывающее нераскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине. Для полученного графа находим новую нераскрашенную вершину из 2-окрестности, если таковая есть, красим ее в ту же краску и объединяем с объединенной вершиной. Такая процедура продолжается до тех пор, пока находятся нераскрашенные вершины в 2 — окрестности объединенной вершины. Затем из числа нераскрашенных вершин выбирается новая вершина, и для нее процедура раскраски повторяется, и так до тех пор, пока все вершины не будут раскрашены.

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