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

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

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

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

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

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

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

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

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

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

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

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

где

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