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

Центры и радиусы графа можно найти непосредственно из матрицы взвешенных расстояний, как было показано в разд. 2 и 3. Приведем два метода нахождения абсолютного центра графа и проиллюстрируем эти методы на примере.

5.1. Метод Хакими [7]

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

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

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

Первый шаг метода осуществляется следующим образом.

Рис. 5.4.

Возьмем ребро графа (см. рис. 5.4). Имеем (из соотношения

поскольку расстояние равно либо длине маршрута, проходящего через вершину либо длине маршрута, проходящего через и являются длинами соответствующих частей ребра

Пусть Поскольку то соотношение (5.8) примет вид

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

и, рассматривая их относительно строим нижнюю «огибающую» для соответствующих им прямых линий.

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

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