Абсолютная медиана графа

Абсолютная медиана — это такая точка на дуге графа, что сумма расстояний от нее до всех вершин графа минимальна.
Теорема. В графе всегда существует вершина, являющаяся абсолютной медианой.
Доказательство. Рассмотрим функцию, характеризующую расстояния точка — вершина d(f— (r, s), j) для каждой вершины j

Вогнутые функции расстояния

В графическом представлении эта функция имеет вид кривой, показанной на рисунке. Заметим, что если соединить любые две точки этой кривой отрезком прямой линии, то этот отрезок всегда будет целиком лежать на кривой или под ней. Любая функция, обладающая таким свойством, называется вогнутой. Кроме того, минимальное значение вогнутой функции всегда находится в одной из ее граничных точек, т. е. либо в точке f =0, либо в точке f=1.
Рассмотрим далее значение СТВ (f — (r, s) = Σ d(f — (r, s), j) как функцию от f. Поскольку эта функция равна сумме вогнутых функций, она также должна быть вогнутой. Таким образом, СТВ(f — (r, s)) достигает минимума либо при f = 0, либо при f = 1. Следовательно, ни одна из внутренних точек дуги (r, s) не может стать абсолютной медианой, а наилучшим претендевтом является одна из ее конечных вершин. Теорема доказана.
Отметим, что доказательство теоремы остается справедливым и в тех случаях, когда вместо расстояний точка — вершина описываемых уравнениями:

d(f—(r,s ), j)=min{f×а_r,s+d_r,j, (1—f)×а_r,s+d_s,j}, для неориентированой дуги

d(f—(r,s ), j) =(1—f)×а_r,s+d_s,j – для ориентированой дуги,

рассматривается любая вогнутая функция от f, характеризующая расстояния точка — вершина. Из теоремы следует, что при поиске абсолютной медианьт достаточно исследовать только вершины графа. Таким образом, любая медиана является также абсолютной медианой, и поэтому для ее отыскания не требуется никаких новых методов.