Алгоритм минимальной раскраски вершин графа

1. Выделяем множество пустых подграфов графа G.

2. Строим двумерную таблицу, каждой строке которой сопоставим взаимно однозначно пустой подграф, столбцу – вершину; в клетке записываем единицу, если j-ая вершина содержится в i-ом пустом подграфе, в противном случае клетку оставляем пустой.

3. Определяем покрытия столбцов строками. Каждое покрытие порождает раскраску. Покрытие минимальной мощности определяет хроматическое число графа G.

Пример. Определить хроматическое число графа G, изображенного на рис. 5.12

Рис. 5.12

□ Для определения хроматического числа сначала необходимо выделить все пустые подграфы заданного графа G. Используя алгоритм выделения пустых подграфов, построим дерево (рис.5.13).

Рис. 5.13

Строим двумерную таблицу:

1 2 3 4 5 6 7

Определяем минимальное число строк, покрывающих все столбцы таблицы. Такими строками могут быть строки 1, 4, 7. Значит

Зададимся красками: для множествами вершин синяя (Син), для множества вершин краска красная ( Кр ), для множества вершин краска зеленая ( Зел ) .

Раскрасим вершины графа G :

Отметим, что вершину 3 можно раскрасить в два цвета: синий или зеленый. ■

Замечание. Аналогично можно определить раскраску ребер графа G и найти минимальную раскраску ребер этого графа G .