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

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

Пусть множество всех таких точек у, лежащих на ребрах графа из которых вершина достижима со взвешенным расстоянием, не превосходящим Таким образом,

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

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

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

Поскольку есть наикратчайшее расстояние между двумя произвольными вершинами то совершенно очевидно, что если меньше половины взвешенного расстояния между

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

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

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

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