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

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

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

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

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

Число внешнего разделения вершины являющейся внешним центром, называется внешним радиусом: число внутреннего разделения внутреннего центра называется внутренним радиусом:

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

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

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

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

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

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

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

то вершину на которой достигается минимум выражения

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

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