3.2. Формулировка задачи о раскраске на языке 0-1-программирования

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

Пусть матрица раскраски графа (задающая некоторую конкретную раскраску вершин графа), так что

Если матрица смежности графа с диагональными элементами, равными 0, то следующие два условия гарантируют допустимость раскраски вершин графа допустимость матрицы раскраски

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

В условии очень большое положительное число (любое целое, большее чем Если вершина окрашена в цвет (т. е. то первый член в (4.12) равен 0. Тогда и второй член должен быть равен 0, чтобы выполнялось неравенство, поскольку числа и неотрицательны. Таким образом, условие (4.12) обеспечивает допустимость раскраски, т. е. если вершина окрашена в цвет то нет смежной с вершины того же цвета. Если вершина окрашена в цвет, отличный от то первый член в (4.12) равен Поскольку второй член в (4.12) не может, очевидно, достигнуть значения (его наибольшее значение равно в действительности то какое бы число вершин смежных с вершиной ни было окрашено в цвет неравенство (4.12) по-прежнему будет выполняться. Заметим, что если вершины смежны с а также смежны между собой, то условие (4.12), записанное для вершины не будет препятствовать раскраске в один и тот же цвет Однако, записав условие (4.12) для мы обеспечим тем самым раскраску этих двух вершин в разные цвета.

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

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

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

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

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

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

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

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

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