2. Медиана графа

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

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

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

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

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

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

По полученным передаточным числам видно, что внешней медианой является и что существуют три внутренние медианы каждая с внутренним передаточным числом, равным 9.

2.1. Выбор места для склада

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

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