3. Кратные медианы (p-медианы) графа

В предыдущей главе, обобщая понятие центра, мы ввели понятие -центра. Подобным же образом можно обобщить понятие медианы, определив -медиану.

Пусть подмножество множества вершин X графа и предположим, что содержит вершин. Как и прежде, введем следующие обозначения:

и

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

так же, как и для одиночной вершины:

где соответственно внешнее и внутреннее передаточные числа множества вершин

Множество для которого

называют внешней -медианой графа аналогично определяется внутренняя -медиана.

Как и в случае -центров, рассмотренных в предыдущей главе, даже для графов средних размеров с вычислительной точки зрения нецелесообразно использовать при нахождении -медиан непосредственно выражения (6.4), (6.5) и (6.6). Алгоритмы построения -медиан будут даны в разд. 5.

3.1. Абсолютные p-медианы

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

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

Сейчас мы докажем [5,6], что не существует точки у, для которой т. е. здесь ситуация противополоясна той, которая имела место при рассмотрении центров.

Теорема 1. Какова бы ни была точка у графа в нем найдется по крайней мере одна вершина для котярой

Доказательство. Пусть у — точка ребра расположенная на расстоянии от Тогда

где длина ребра

Пусть множество тех вершин для которых первый член в (6.7) не больше второго, множество вершин, для которых второй член меньше первого. Мы можем тогда написать

Поскольку из неравенства треугольника следует, что

то, заменяя на в выражении (6.8), получаем

Так как то, сделав перегруппировку в (6.10), имеем:

Поскольку для каждого ребра мы вправе сами решать, какую вершину называть и какую то всегда можно добиться выполнения неравенства

Заметив, что первый член в правой части неравенства (6.11) равен получаем из (6.11) такое соотношение:

Таким образом, для вершины величина не превышает следовательно, теорема доказана.

Теорема 1 довольно просто обобщается на случай -медиан.

Теорема 2. Каково бы ни было множество состоящее из точек графа т. е. из точек ребер и вершин, найдется по крайней мере одно подмножество , содержащее вершин, для которого

В теоремах предполагалось, что передаточные числа определены с помощью выражений (6.1) и (6.5). В работах Леви [20], Голдмана 112] и Голдмана и Мейерса [14] было показано, что эти теоремы остаются в силе и в тех случаях, когда передаточные числа определяются как суммы произвольных, вогнутых функций от взвешенных расстояний.

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