5.2. Размещение аварийных служб (общий случай)

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

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

Очевидно, что центром графа является либо вершина либо и что радиус графа равен 8.

Сначала возьмем ребро (рис. 5.5), и пусть расстояние измеряется от вершины до вершины

Выражения и из соотношений (5.10) (для имеют в нашем случае такой вид:

Рис. 5.5. Граф из примера разд. 5.2.

аналогично

Графики этих функций изображены на рис. 5.6а, для Имеются два локальных абсолютных центра у на расстоянии 6 и 8 минут от Число разделения этих двух центров равно 8 минутам.

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