Абсолютный центр

Абсолютный центр — это любая точка на дуге, расстояние от которой до наиболее отдаленной вершины графа минимально. Для поиска абсолютного центра мы должны найти такую точку f — (r, s), что максимальное расстояние точка-вершина для нее должно быть минимальным.

МТВ(f — (r, s)) = min{МТВ(f — (t, u))}.

Задача поиска абсолютного центра явдяется более трудной, чем задачи поиска центра и главного центра графа, так как в процессе ее решения необходимо просматривать не только вершины, но и все точки дуг графа. Рассматривая свойства решения задачи, отметим, что ни одна из внутренних точек ориентированной дуги не может быть абсолютным центром. действительно, из того, что обход ориентированной дуги может производиться только в одном направлении, следует, что конечная вершина, в которую входит эта дуга, ближе к каждой вершине графа, чем любая внутренняя точка этой дуги. Следовательно, при поиске абсолютного центра мы должны рассматривать только вершины графа и внутренние точки его неориентированных дуг. Рассмотрим произвольную неориентированную дугу (r, s). Расстояние d(f — (r, s), j) от точки f на дуге (r, s) до вершины j определяется из уравнения:

d(f—(r,s ), j)=min{f×а_r,s +d_r,j, (1—f)×а_{r, s}+d_s,j},

где а_r,s– длина дуги (r, s); d_r,j– длина минимального пути между вершинами r, и j. Это расстояние легко представить как функцию от f. Ее график представляет собой кусочно-линейную кривую с не более чем двумя линейными отрезками. Построим графики d(f — (r, s), j) для 0≤f≤1 и для всех j. Участки кривых каждого из графиков, которые лежат выше соответствующих участков кривых всех других графиков, представляют собой значения max d(f — (r, s), j) для всех f. Точка f* дуги (r, s), в которой достигается минимальное по f значение max d(f — (r, s), j), является наилучшим претендентом на размещение в ней абсолютного центра на дуге (r, s). С помощью этой процедуры может быть найдена точка размещения наилучшего претендента на каждой неориентированной дуге графа.
Абсолютным центром является любая точка f* — (r, s)*, для которой расстояние до максимально удаленной вершины графа минимально, т. е.

max{d(f*— (r, s)*, j) = min{max{d(f* — (t, u), j)}}

Таким образом, абсолютный центр находится в два этапа. Сначала находятся на каждой неориентированной дуге точки — претенденты на размещение в них абсолютного центра. Точками-предендентами являются точки на дуге, расстояние от которых до наиболее удаленных вершин минимально. Затем среди этих претендующих точек и всех вершин графа в качестве абсолютного центра выбирается такая точка или вершина, расстояние от которой до максимально удаленной вершины графа минимально, для выбора наилучшей претендующей точки на каждом ребре требуется построение функций, характеризующих расстояния точка — вершина для всех f-точек. Это относительно не сложная процедура, так как функции являются кусочно-линейными кривыми, содержащими не более двух отрезков. К сожалению, по-видимому, не существует неграфических методов определения наилучших точек-претендентов, где можно было бы избежать сравнения на графиках расстояний точка — вершина для различных вершин графа. Рассмотренный метод отыскания абсолютного центра был предложен Хакими в 1964 г.
Алгоритм

1. 1. находим D⁰ – матрицу, элементами которой являются a_i,j – длины кратчайших дуг.
   2. Ищем   D^N –  матрицу длин кратчайших расстояний по Флойду или Данцигу.
   3. находим наилучшего претендента на роль абсолютного центра среди вершин графа (ищем вершину, являющуюся центром)
   4. исследуем внутренние точки неориентированых дуг графа. строим для каждого ребра функциональные зависимости расстояния точка-вершина на основе уравнения:
      d(f—(r,s ), j)=min{f×а_r,s +d_r,j, (1—f)×а_{r, s}+d_s,j}Аргументом функции является f.
   5. Строим в одной системе координат графики всех функций полученных для исследуемого ребра (их число равно числу вершин графа), определяем верхнюю границу max d(f — (r, s), j).
   6. определяем точку f* в которой достигается наименьшее значение верхней границы max d(f — (r, s), j)
   7. возвращаемся к пункту 4, пока не исследуем все неориентированые дуги графа
   8. Из полученых вариантов среди вершин графа и его внутренних точек выбираем наилучший. Критерием выбора является наименьшее значение расстояния до наиболее удаленной вершины графа.

Пример