Если А = [aft] - матрица смежности графа G с диагональными элементами, равными О, то следующие два условия гарантируют допустимость раскраски вершин графа G (т. е. допустимость матрицы раскраски [tj])-

(для Bcexi = l, ...,п), (4.11)

f ДЛЯ всех 1 = 1, . .., п

L-{i-hj)-a,kUj>0[ / = 1,2,... . (-12)

Условие (4.11) обеспечивает раскраску вершины в ОДИН и только один цвет.

В условии (4.12) L - очень большое положительное число (любое целое, большее чем п). Если вершина Xi окрашена в цвет / (т. е. = 1), то первый член в (4.12) равен 0. Тогда и второй член должен быть равен О, чтобы выполнялось неравенство, поскольку числа ttik и Ijjj неотрицательны. Таким образом, условие (4.12) обеспечивает допустимость раскраски, т. е. если вершина х^ окрашена в цвет /, то нет смежной с вершины того же цвета. Если вершина Xi окрашена в цвет, отличный от / {1ц = 0), то первый член в (4.12) равен L. Поскольку второй член в (4.12) не может, очевидно, достигнуть значения L (его наибольшее значение равно в действительности п - 1), то какое бы число вершин х^, смежных с вершиной Xi, ни было окрашено в цвет /, неравенство (4.12) по-прежнему будет выполняться. Заметим, что если вершины xk и Xk смежны с Xi, а также смежны между собой, то условие (4.12), записанное для вершины Xi, не будет препятствовать раскраске Xk и xh в один и тот же цвет /. Однако, записав условие (4.12) для xk (или х1), мы обеспечим тем самым раскраску этих двух вершин {х{ и xk) в разные цвета.

Пусть теперь каждому цвету / сопоставлен штраф pj, выбранный так, что

Pj+i>h-pj (штраф Pi принят равным единице) (4.13)

и где h есть верхняя оценка для наибольшего числа вершин в графе, которые могут быть окрашены в один цвет, r.e.h- произвольное число, большее чем а (G) - число независимости графа. При отсутствии лучшей оценки можно положить h = п, не проводя лишних вычислений.

Задача раскраски вершин графа с использованием наименьшего числа цветов может быть сформулирована следующим образом:

минимизировать

z=S S Pjhj (4.14)

j=l i=l

при ограничениях (4.11) и (4.12).

Минимизация выражения (4.14) обеспечивает выполнимость следующего условия: цвет / + 1 не будет использован в раскраске вершин, если цвета от 1 до; достаточны для допустимой раскраски. Матрица (раскраски графа) которая дает решение приведенной выше задачи линейного 0-1-программирования, определяет оптимальную раскраску, а используемое при этом число цветов равно хроматическому числу графа.

Берж [1] вместо условия (4.12) предложил следующее:

f для всех к = \,2, ..., т

/-<Чи / = 1,2,... , (-15)

где [bik\ -матрица инциденций, т. е. bik = 1, если вершина инцидентна ребру а^, и bik = О в противном случае. Услов-вие (4.15) отражает тот факт, что не более чем одна из двух концевых вершин любого ребра может быть окрашена в цвет /.

Хотя это условие более естественное, чем (4.12), но для его описания требуются mq ограничений, тогда как для условия (4.12) нужно только nq ограничений. Поскольку число ребер (т) связного графа обычно значительно больше числа его вершин (п), то условие (4.12) с вычислительной точки зрения предпочтительнее. Насколько велик при этом выигрыш, можно увидеть на следующем примере: если в некотором 100-вершинном графе число ребер будет составлять только 20% от числа ребер в полном 100-вершинном графе, то для задания условия (4.15) потребуется 1000 ограничений на каждый цвет, а для описания условия (4.12) - только 100 ограничений на каждый цвет.

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

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

Итак, пусть построены все максимальные независимые множества графа G, например с помощью алгоритма, приведенного в разд. 2.3 предшествующей главы (пусть таких множеств t), и пусть задана (п X г)-матрица М = 1тtj], у которой mj = 1, ели вершина Xt принадлежит /-му максимальному независимому множеству, и тц = О в противном случае. Если теперь каждому максимальному независимому множеству сопоставить единичную стоимость, то задача раскраски сведется просто к задаче нахождения наименьшего числа столбцов в матрице М, покрывающих все ее строки ). Каждый столбец из решения этой ЗНП соответствует определенному цвету, который может быть использован для окраски всех вершин максимального независимого множества, представленного этим столбцом.

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

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

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

М

т т т

) Напоминаем, что i-й столбец в 0-1 -матрице покрывает те и только те строки, в которых на пересечении с i-м столбцом стоят единицы.- Прим. ред.