3.3. Сведение задачи о раскраске к ЗНП

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

Итак, пусть построены все максимальные независимые множества графа например с помощью алгоритма, приведенного в разд. 2.3 предшествующей главы (пусть таких множеств и пусть задана -матрица , у которой вершина принадлежит максимальному независимому множеству, и в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице покрывающих все ее строки Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.

Хотя число столбцов матрицы может быть весьма велико даже для графов средних размеров, формулировка задачи раскраски как ЗНП предпочтительнее, чем непосредственная ее постановка как задачи общего 0-1-программирования, потому что ЗПН могут быть решены для таких размеров (т. е. для числа переменных), которые по крайней мере на порядок больше, чем «подходящие» размеры в случае задач общего 0-1-программирования (см. гл. 3).

3.3.1. Пример. Для графа, изображенного на рис. 4.4, число всех максимальных независимых множеств равно 15, и в матрице, приведенной ниже, они представлены столбцами; на пустых местах в матрице должны стоять нули.

Максимальные независимые множества

Рис. 4.4. Граф из примера 3.3.1.

Решение задачи о покрытии для этой матрицы состоит из

4 столбцов и не является единственным. Например, решениями будут множества столбцов

Если мы выберем последнее из этих решений (отмеченное стрелками) и сопоставим цвета столбцам 4, 6, 10 и 2 соответственно, то вершину (принадлежащую одновременно столбцам 2 и 4) можно окрасить в цвет а или в цвет а вершину (принадлежащую обоим столбцам 2 и 10) можно окрасить в цвет с или в цвет и таким образом получить различные оптимальные раскраски.

Интересно отметить, что в данном примере нижняя оценка для равна 4 (это можно получить из соотношения (4.2), так как значит, совпадает с истинным значением