Всякому локальному центру, расположенному на ребре (Xi, Xj), соответствует (как видно из соотношения (5.8), если положить все длины I равными нулю) его абсолютный локальный радиус (скажем, г^), который не меньше, чем ptj, где

Pij = шах [i;smin {d (х„ xj), d {х„ Xj)}]. (5.11)

Таким образом, pt j есть нижняя оценка абсолютного радиуса графа, если абсолютный центр лежит на ребре (xj, xj). Следовательно, величина

Р= max [pij] (5.12)

(где A -множество ребер графа) является обоснованной нижней оценкой абсолютного радиуса графа.

Допустим, что абсолютный центр расположен в середине ребра (Xi, Xj). Тогда, в силу соотношения (5.8), абсолютный радиус равен

Pij + Vs*Cij, где Vg* - вес той вершины х в которой достигается

наибольшее значение величины pij, указанной в соотношении (5.11). Следовательно,

Я= min [Pij + v,iCij] (5.13)

(.Xi,xj)eA

является обоснованной верхней оценкой абсолютного радиуса графа. Таким образом, всякое ребро (х^, Xj, для которого Pi j Н, может не рассматриваться при поиске абсолютного центра.

Для графа, приведенного на рис. 5.5, у которого = 1 для всех Xi 6 X, получаем (используя формулу (5.11)) следующие результаты:

центр на = (xg, х^) дает ps,i - max (2, 6, 2) = 6, центр на = {21 з) дает /?2,з = max (8, 10, 6) = 10, центр на = (х^, х^) дает /?5,2 = шах (2, 2, 4) = 4, центр на == (х^, х^) дает p.s = max (6, 8, 4) == 8, центр на = (х^, х4) дает Pi,i = max (8, 8, 2) = 8, центр на = (х^, х^) дает 4,5 = max (2, 6, 8) = 8.

Верхняя оценка Я равна, следовательно (в силу соотношения (5.13)),

min (6 -f 4, 10 -f 1, 4 -f 3, 8 + 1, 8+3, 8+2) = 7,

и поэтому ребра а^, а^, и а^, для которых pij > 7, могут быть исключены из списка кандидатов на размещение абсолютного центра. Поиск абсолютного центра нужно вести только на двух оставшихся ребрах (так, как это было продемонстрировано рань-

ше и показано на рис. 5.6 (а) и 5.6 (в)). Используя верхние и нижние оценки, удалось уменьшить поиск в 3 раза. Наименьшая нижняя оценка Р, вычисленная но формуле (5.12), равна

Р = min (6, 10, 4, 8, 8, 8) = 4.

Эта оценка не является точной, поскольку истинная величина абсолютного радиуса г данного графа (найденная в разд. 5.2) равна 6.

5.4. Итерационный метод

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

Пусть Q) (xj) - множество всех таких точек у, лежащих на ребрах графа G, из которых вершина достижима со взвешенным расстоянием, не превосходящим X. Таким образом,

Qx{xi) = {y\Vid{y,Xi)X, г/-точка графа G}. (5.14) Это выражение похоже на те (см. (5.1)), с помощью которых были определены множества RI (xj) и Ri (xj); отличие состоит в том, что теперь у - любая точка графа G, а необязательно его вершина. Абсолютный радиус г, очевидно, является наименьшим значением Я при котором из некоторой точки у графа G все верширы графа могут быть достигнуты со взвешенным расстоянием, меньшим или равным X. Следовательно, г есть такое наименьшее значение X (скажем, Х^щ), что

П [<?; (01 = Qx (i) П Qx ix2) n n <?; (Xn) Ф 0. (5.15)

Поэтому можно начать с произвольного небольшого значения Я строить множества Q% (Xj) для всех г = 1, 2, . . ., тг и проверять, выполняется ли соотношение (5.15). Если оно не выполняется, то надо увеличить немного величину Я заново построить множества Q% (Xj) (при новом значении Я,) и опять проверить, не выполняется ли соотношение (5.15). Эту процедуру можно повторять до тех пор, пока не будет выполняться (5.15). Полученная таким образом величина Я, принимается за абсолютный радиус г графа G. Более того, поскольку приращения величины А. малы, то пересечение

П {QUi)] (5.16)

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

Kq = шах

XjiXi.

-d{Xi,Xj)], (5.17)

L Vi+Vj

поскольку радиус г должен быть не меньше К^. С этой точки зрения, значение б = 2Яо можно назвать диаметром графа. Нужно, однако, отметить, что совсем необязательно диаметр графа в два раза больше значения абсолютного радиуса (определенного в разд. 4, см. в связи с этим задачу 5.11).

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

6. Кратные центры (/?-центры)

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

Пусть Xj,- подмножество (содержащее р вершин) множества X вершин графа G = (X, Г). Через d (Хр, xi) будем обозначать наикратчайшее из расстояний между вершинами множества Хр и вершиной Xj, т. е.

d{Xp,Xi)= min ld{Xj,Xi)].

jEp 1277

Аналогично, символом d (х;, Хр) обозначается min Id (х;, Xj)].

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

So (А'р) = max [Vjd (Хр, х-)]

St{Xj,) = maxlVjd{Xj,Xj,)],

xjex

где So (Хр) и Sj (Хр) - числа внешнего и внутреннего разделения множества Xj,.

Поскольку d [xi, Xj) есть наикратчайшее расстояние между двумя произвольными вершинами Х; и Xj, то совершенно очевидно, что если Я, меньше половины взвешенного расстояния между Х; и Xj, т. е.

<~<ii=i) Qx{Xi)r]QaXj) = 0

и полное пересечение множеств в выражении (5.16) пусто.

Следовательно, итерационный процесс поиска абсолютного центра можно начать со значения Л, равного