4. ПРИБЛИЖЕННЫЕ АЛГОРИТМЫ РАСКРАПШВАНИЯ 91

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

В этой процедуре молчаливо предполагалось, что если две вершины имеют одинаковые степени, то их взаимное положение в списке случайно. В таких ситуациях уточнение в размещении вершин можно осуществлять с помощью двухшаговых степеней вершин Xi, имеющих одинаковые степени (одинаковые 1-шаговые степени), где di определяется как число маршрутов ) длины 2, исходящих из Xi. Эти вершины могут быть размещены тогда в соответствии с величинами степеней Й1 \ Если все-таки найдутся вершины, у которых совпадают и степени d и степени df, то можно вычислить трехшаговые степени df (определяемые аналогичным образом) и разместить вершины с учетом степеней df и т. д.

Можно действовать иначе: размещать вершины сразу в соответствии с их степенями dS или степенями df и применять тот же самый последовательный метод раскраски [24 . Таким образом, описанный выше метод раскрашивания очерчивает целый класс последовательных методов, каждый из которых связан с определенным способом упорядочивания вершин, либо статическим, т. е. фиксированным сразу для всей процедуры, либо динамическим, т. е. изменяющимся в процессе раскраски. Способ упорядочивания может базироваться на многих возможных критериях, зависящих от степеней вершин или от каких-либо других родственных характеристик. Результаты вычислений и сравнение последовательных методов раскрашивания для графов, выбранных случайным образом, приведены в работах Матулы, Марбле и Исааксона [16] и Вильямса [24]. Границы применимости этих эвристических методов демонстрируются у Митчема [17], показавшего, что можно построить графы, для которых любой из эвристических методов дает произвольно плохие оценки хроматического числа.

1) Если А - матрица смежности графа G с диагональными элементами, равными О, то = 2 <Ц- Двухшаговая степень определяется тогда по фор-

муле di = У\ Oijdj, и вообще fc-шаговая степень определяется по рекуррент-НОИ формуле:

df)= ] aijdf-\ ;=1

5. Обобщения и приложения

Задача раскраски в том чистом виде, в каком она рассматривалась выше в настоян];ей главе, редко встречается на практике. Однако ее обобп];ения и разновидности (незачительно отличаю-щаеся от нее) находят широкое применение в большом числе различных прикладных задач. Целью данного раздела является ознакомление читателя с несколькими наиболее часто встречаю-п];имися обобп];ениями. Список приложений, естественно, этими примерами не ограничивается.

5.1. Простая задача размещения (загрузки) [6]

Рассмотрим задачу размещения (загрузки) п каких-то предметов по ящикам. Пусть каждый предмет соответствует определенной вершине графа G. Всякий раз, когда два предмета Х; и Xf не могут быть размещены в одном ящике (например, когда предмет Xi может загрязнить предмет xj), в граф G вводится ребро {xi, Xj). Если ящики имеют неограниченную вместимость, так что в каждый из них можно поместить сколько угодно предметов, то задача нахождения наименьшего числа ящиков для размещения предметов эквивалентна задаче нахождения хроматического числа графа G; причем каждому ящику соответствует определенный цвет , а предметы, окрашенные в один цвет, укладываются в один и тот же ящик.

(i) Ящики одинаковой вместимости. В действительности ящики обладают ограниченной вместимостью. Предположим, что вместимость одинакова у всех ящиков и равна Q. Это можно интерпретировать так: в один цвет окрашиваются не более чем Q вершин. В терминах 0-1-программирования (см. разд. 3 настоящей главы) данная задача загрузки может быть сформулирована следующим образом:

минимизировать выражение (4.14) при ограничениях (4.11), (4.12) и

п

(для всех 7 = 1,2, ...,q). (4.16)

Решением этой задачи является матрица [у], описывающая оптимальное размещение (распределение) предметов по ящикам (иначе говоря, группировка предметов по цвету). Число q есть верхняя оценка для числа ящиков.

(ii) Ящики имеют, вообще говоря, различные вместимости, и ящикам приписаны стоимости. Пусть 7-й ящик илюет вместимость Qj и стоимость Vi. Предположим еще, что предметам (верши-

1) Задача о ранце рассматривалась, например, в [10].

нам графа) сопоставлены веса, скажем, г-му предмету соответствует вес и>1. Требуется так разместить предметы по ящикам, чтобы

(а) выполнялись условия, накладываемые графом G,

(б) удовлетворялись ограничения на вместимость ящиков,

(в) была наименьшей общая стомимость используемых ящиков. Тогда задача примет следующий вид:

д

минимизировать функцию г=2Ф^ (4-17)

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

(4.18)

S для всех 7 = 1,

з^Щ) (4.19)

где переменная ypj принимает значение 1, если в ящик / помещен какой-либо предмет, и равна О в противном случае.L - произвольное положительное целое число, большее, чем п, а q - общее число имеющихся ящиков. Ограничение (4.18) означает, что ни один из ящиков не перегружается, а ограничение (4.19) гарантирует выполнимость условия: если -ф^о = О (т. е. ящик /о пуст), то все lijo (г = 1, . . ., п) также равны 0.

В этом самом общем случае необходимо было ввести дополнительные переменные \pj, поскольку ящики (цвета) нельзя штрафовать тем способом, который характеризуется выражением (4.14). Следует отметить, что чем более общей является задача, тем менее важным становится ее раскрасочный аспект. Так, например, в только что рассмотренной задаче можно выделить две подзадачи:

(а) о раскраске , соответствующую ограничению (4.12), и

(б) о ранце , определяемую ограничением ) (4.18). Два других ограничения, (4.11) и (4.19), являются ограничениями структурного характера.

Из-за этих двух взаимосвязанных аспектов общая задача раскраски значительно труднее для решения, чем чистая задача раскраски.

Две следующие прикладные задачи можно рассматривать как задачи о раскраске графа (или соответствующие обобщения задачи о раскраске).