Раскраска графа.

Постановка задачи

В теории графов раскраска графов является частным случаем разметки графов. При раскраске элементам графа ставятся в соответствие метки с учётом определенных ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин.

Дано:

•  Неориентированный граф с вершинами и ребрами.

•  Набор цветов, в которые могут быть окрашены вершины графа. Верхняя оценка равна максимальной степени вершин графа + 1 (оценка жадного алгоритма).

Требуется:

Найти раскраску вершин графа минимальным числом цветов так, чтобы соседние вершины имели разный цвет.

кратко