5.3. Модифицированный метод Хакими

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

(кликните для просмотра скана)

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

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

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

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

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

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

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

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

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

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