предъявляет больших требований к памяти машины и позволяет уменьшить время вычисления, особенно при выполнении шага 5 алгоритма. Если абсолютный р-центр описан на языке строгих пересечений , то дальнейшая процедура осуществляется чрезвычайно просто: надо лишь выяснить, какие участки ребер соответствуют этим строгим пересечениям.

На шаге 4 алгоритма надо строить двудольный граф <т' = (X \J X, А'), у которого вершины из X представляют области Ф^. Это может привести к графу больших размеров, что сильно увеличит время вычисления на шаге 5. Однако с помощью приводимой ниже теоремы удается уменьшить размеры графа G: исключаются те области, которые не влияют на получаемое оптимальное решение (но если существует больше одного оптимального решения, то при такой процедуре некоторые из них можно потерять). Другие пути, позволяющие достичь определенных упрощений, описаны в разд. 4.2 гл. 3.

Теорема 1. При заданной величине К для получения некоторого минимального доминирующего множества графа G можно предварительно исключить из множества X все вершины, соответствующие тем SI, над которыми доминируют другие SI в X. Мы говорим, что (SI)i доминирует над (SI), если (SI)j <8) (SI)2 = (SI)2, где ® означает булевское произведение.

Доказательство этой теоремы очевидно.

В алгоритме из предыдущего раздела параметр к при каждой очередной итерации увеличивается (по понятным причинам) лишь на небольшую величину. Существует много других более эффективных способов варьирования параметра X. Результаты вычислений, приведенные в разд. 8.4, получены с помощью программы, использующей направленный двоичный поиск по А..

8.3. Пример

Рассмотрим граф G, изображенный на рис. 5.8. Число, стоящее около любого ребра, задает его длину; вес каждой вершины графа равен единице. Требуется найти абсолютный р-центр с минимально возможной величиной параметра р и такой, чтобы каждая вершина графа отстояла хотя бы от одного из этих р центров на расстоянии, не превосходящем 3,5 единиц.

Для К = 3,5 на рис. 5.9 показаны метки, определяющие множества Q}, (xi). Они расставлялись сразу же в процессе последовательного прохождения ребер. Числа в кружках, стоящие около произвольной метки, указывают номера вершин, которым эта

метка соответствует. Так, кружок @ на ребре (2,3) означает, что

Рис. 5.8. Граф из примера 8.3. Номера вершин подчеркнуты. Все другие числа являются длинами ребер.

ТОЛЬКО отмеченная точка достижима из вершин 1 и 3 в пределах расстояния 3,5. На рис. 5.9 точками около ребер показано достижимое множество Qx (5), соответствуюп1;ее вершине 5. Всего в данном примере суп1;ествует 33 участка ребер, включая пустой участок (из которого ни одна вершина не может достигаться в пределах расстояния 3,5 единиц). Пустой участок расположен между метками 4 и 5 на ребре (4,5). Некоторые из этих 33 участков имеют

Рис. 5.9. Метки для достижимых множеств. Множество Qx (5) отмечено точками.

одинаковые SI; существует всего 18 областей со следующими SI

(1) 000000

(2) 010000

(3) 001000

(4) 000100

(5) 000010

(6) 000001

(7) 000011

(8) 110000

(9) 001100 (10) 100010 (И) 011000 (12) 010001

(13) 000101

(14) 001001

(15) 111000

(16) 011100

(17) 110010

(18) 100011

Так, например, участок между метками 1 и 6 на ребре (1,5) принадлежит области с SI, равным 100011, поскольку лишь из точек графа, лежащих между этими двумя метками, можно достигнуть вершины 1, 5 и 6 (и никакие другие) в пределах расстояния X = 3,5.

После исключения тех SI, которые доминируются другими SI, остается только 7 областей (с номерами SI от 12 до 18). Граф G

3 4 5

вершины графа С

Рис. 5.10. Граф G из примера 8.3. Области в наименьшем доминирующем множестве.

после выполнения шага 4 алгоритма выглядит так, как показано на рис. 5.10. Для нахождения наименьшего доминирующего множества этого графа можно воспользоваться алгоритмом, описанным в гл. 3 и предназначенным для решения задачи о наименьшем покрытии. Однако в нашем (простом) примере наименьшее множество легко строится с помощью прямого последова-