Для каждой вершины х,- определим следующие два числа:

So {Xi) = mAx[Vjd (xi, Xj)] St (Xi) = max [vjd (xj, Xj)].

(5.2)

Числа So (xi) и Sj (xi) называются соответственно числом внешнего разделения и числом внутреннего разделения вершины Xi. Следует отметить, что (х>) является наибольшим числом в строке Xi матрицы В' (G), полученной в результате умножения каждого столбца / матрицы расстояний D (G) == [d {Xi, xj)] на Vj, и St (Xi) является наибольшим числом в столбце xt матрицы D (G), полученной после умножения каждой строки / матрицы расстояний D (G) на Vj.

Рассмотрим в качестве примера ориентированный граф, изображенный на рис. 5.1, и предположим, что все веса вершин и дуг графа равны единице. Матрица расстояний графа имеет вид

3 3 4 3

D{G)

s.{x,)

4 3* 3* 4 3* 3*

Числа внешних и внутренних разделений приведены в присоединенных к матрице столбце и строке соответственно.

Если Хо - наименьшая длина Я, такая, что для вершины Xj

Rl{Xi) = X

(т. е. все вершины графа G достижимы из Xi с использованием путей, взвешенные длины которых не превосходят Хд, причем Хо - наименьшее из таких чисел), то из соотношений (5.1) и (5.2) следует равенство

So (Xi) = Хо.

(5.3)

Аналогично, если Я,( - такая наименьшая длина К, что Ri{xi) = X,

то St (xi) = Kf

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

3. Центр и радиус

Вершина х*, для которой

s,{x*) = mm[s,{xi)], (5.4(a))

называется внешним центром графа G; и аналогично вершина х*, для которой

St (хГ)== min [St (Xi)], (5.4(6))

называется внутренним центром графа G.

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

Число внешнего разделения вершины х*, являющейся внешним центром, называется внешним радиусом: ро = s (х*); число внутреннего разделения внутреннего центра называется внутренним радиусом: Pt~t (х*)-

У графа, изображенного на рис. 5.1, с матрицей расстояний, приведенной выше, имеются только один внешний центр (вершина х^) и четыре внутренних центра, образующих множество {х2, Хз, х^, Xq). Внешний радиус графа равен 2, а внутренний 3.

3.1. Размещение аварийных служб и пунктов обслуживания

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

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

время проезда может зависеть от уклонов на дороге, наличия улиц с односторонним движением и т. д.

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

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

Sot (Xi) = max {vj [d (xt, Xj) + d {Xj, Xi)]}, TO вершину Xot, на которой достигается минимум выражения

SotiXi),

можно назвать внешне-внутренним центром.

Для графа, изображенного на рис. 5.1, с матрицей расстояний D (G), приведенной ранее, внешне-внутренним центром является вершина х^. Внешне-внутренний радиус равен 5.

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

Соотношение (5.3) определяют числа разделения для любой вершины Xi 6 X. Мы обобщим теперь это определение на случай

а

Xi о---*---о xj

У

Рис. 5.2. Размещение на дуге.

искусственных точек, которые можно помещать на дугах. Итак, если а = (Xi, Xj) (см. рис. 5.2) представляет дугу графа с весом (длиной) Сц, то точка у, помещаемая на этой дуге, может быть определена посредством задания длины I (х;, у) участка (ж;, у) причем должно выполняться равенство

l(xi,y) + Hy,Xj) = Cij. (5.5)

Числа разделения s (у) и Sj (у) точки у независимо от того, является она вершиной графа G или искусственной точкой дуги