Множество Хра, для которого

s<,(X*o)= min К(Хр)], (5.19)

называется р-кратным внешним центром графа G; аналогично определяется р-кратный внутренний центр Xpt.

В разд. 2 и 3 указывалось, что центры графа легко могут быть получены из матрицы взвешенных расстояний. Однако находить таким же способом (полным перебором) р-центр можно лишь для небольших графов и для небольших значений величины р. При таком подходе надо построить всевозможные множества вершин Хр X, содержащие р вершин, а затем, используя формулы (5.18) и (5.19), непосредственно найти множества Хро и X*t, образующие р-центры. Если предположить, что матрица расстояний уже известна, то непосредственное применение соотношений (5.18)

и (5.19) потребует выполнить р-{п-р) j сравнений. Это

число при п = 100 и р = 5 равно 3,58-10 , что значительно превышает возможности существующих ЭВМ.

6.1. Задача размещения нескольких пунктов обслуживания

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

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

Если предположить, что пожарные должны размещаться в вершинах соответствующего графа G, то задача будет состоять в нахождении р-центров графа для р = 1, 2, 3, ... и т. д. до тех пор, пока число разделения р-центра не станет меньше или равно заданному расстоянию. Полученное (последнее) значение числа р будет наименьшим числом пожарных депо, а р-центр - их оптимальным размещением, удовлетворяющим предъявляемым требованиям.

Алгоритм нахождения р-центров является частным случаем алгоритма решения более общей задачи, состоящей в определении

7. Абсолютные /?-центры

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

Задача нахождения абсолютного р-центра может быть сформулирована следующим образом.

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

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

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

Это - общая задача определения абсолютных р-центров. Именно она наиболее часто встречается на практике. Однако решать ее гораздо труднее, чем какой-либо из ее ограниченных вариантов. Метод Хакими [7, 8], приведенный в разд. 5 и предназначенный для решения задачи с одним абсолютным центром, не может быть обобщен на случай абсолютных р-центров. Для нахождения таких центров Сингер [12] предложил некоторый эвристический метод.

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

(i) Процесс можно закончить сразу же, как только достигнута необходимая точность в расположении центров.

8 н. Кристофидес

р-центров, располагающихся, вообще говоря, не в вершинах графа. Рассмотрение общего алгоритма поиска р-центров мы отложим до разд. 8.5, пока не будет исследована соответствующая более общая задача.

где

d{Yp,Xj)= min [d(yi,xj)].

Абсолютный р-центр графа G определяется как множество точек Yp, для которого

s(Y*p)= min [s{Yp)]. (5.21)

Yp на G

8. Алгоритм нахождения абсолютных /-центров

Рассмотрим по очереди каждую вершину Xi и углубимся по всем возможным маршрутам, выходящим из нее, на расстояние б г = X/vi, где X - заданная константа, которую мы будем называть константой троникновения .

Пусть (Xi) - множество всех точек у на графе G, из которых вершина Xi достижима в пределах расстояния при заданном значении X. Множества Q, (Xi) определяются с помощью соотношения (5.14) из разд. 5.2. Эти множества весьма легко можно построить, применяя алгоритм, подобный алгоритму Дейкстра [4] (позволяющему находить кратчайшие пути в графе, см. гл. 8).

Определим область как множество таких точек у на графе G, что из каждой точки у достижимо в пределах расстояния ) б^ (при заданном X) одно и то же множество вершин графа G. Область может быть, например, частью ребра или может содержать только одну точку. Рассмотрим в качестве примера граф, изображенный на рис. 5.7. Пусть все веса вершин равны единице, а длины ребер равны Ci,2 = 4, С2,з = 8 и Cgj = 6. Возьмем X = 3. Тогда 6j = 3 для всякого i и существует шесть различных областей.

) В дальнейшем (в тех случаях, когда не могут возникнуть недоразумения) слова в пределах расстояния... при заданном Я опускаются.- Прим.

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

Ради упрощения обозначений мы будем рассматривать только неориентированные графы. Распространение полученных результатов на ориентированные графы осуществляется очевидным образом.

Пусть Yp - произвольное множество каких-либо р точек на графе G. Число разделения s (Yp) множества Yp определяется так:

S (Yр) = mm [vjd(Yp,Xj)], (5.20)