3.4 Сведение задачи о раскраске к задаче о наименьшем покрытии

Поскольку при любой допустимой раскраске графа G множество вершин, окрашиваемых в один и тот же цвет, должно быть независимым множеством, то всякую допустимую раскраску можно интерпретировать как разбиение всех вершин графа G на такие независимые множества. Далее, если каждое независимое множество расширить до максимального (путем добавления к нему других вершин), то раскраска графа G может быть тогда истолкована как покрытие вершин графа G максимальными независимыми множествами. Очевидно, что в последнем случае некоторые вершины графа G могут принадлежать более чем одному максимальному независимому множеству. Это говорит о возможности существования различных допустимых раскрасок (использующих одно и то же число цветов), так как вершину, принадлежащую разным максимальным множествам, можно окрасить в любой из цветов, соответствующих тем максимальным независимым множествам, которым она принадлежит.

Итак, пусть построены все максимальные независимые множества графа G (пусть таких множеств t), и пусть задана (n×t) матрица M = {m_ij}, у которой m_ij=1, если вершина x_i принадлежит j-му максимальному независимому множеству, и m_ij=0 в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице М, покрывающих все ее строки х). Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.

Приведем пример (рисунок 1):

Рисунок 1

Для данного графа матрица M будет иметь следующий вид (рисунок 2):

Рисунок 2 – матрица графа

Решениями будут являться такие комбинации столбцов, чтобы столбец, состоящий из дизъюнкций соответствующих элементов представлял бы собой столбец из единиц. Например такими множествами будут {4,6,10,14}, {4,6,10,12}, {4,6,10,11}, {4,6,10,8} и {4,6,10,2}.