Главная медиана графа

Главная медиана — это такая вершина х, что сумма расстояний от нее до каждой из дуг минимальна. Под расстоянием от вершины до дуги понимается максимальное расстояние от вершины до точек на этой дуге. Таким образом, главная медиана — это такая вершина х, что

СВД (х) = min {СВД (i)}.

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

d'(j, (r, s))= d_j,r+ d_j,s +a_r,s/2,

если дуга (r, s) ориентированная и

d'(j, (r, s))= d_j,r+ a_r,s,

если дуга (r, s) неориентированная.
Алгоритм поиска главной медианы

1. 1. находим D⁰ – матрица, элементами которой являются a_i,j – длины кратчайших дуг.
   2. расчитываем D^N –  матрицу длин кратчайших путей между всеми вершинами графа по Флойду или Данцигу.
   3. определяем элементы матрицы D’ (матрица, элементами которой являются расстояния вершина-дуга)
   4. Находим СВД(i) для каждой вершины графа
   5. Выбираем минимальное СВД(i) из найденых нами – соответствующая вершина является главной медианой графа.

Пример
Необходимо определить главную медиану для графа представленого на рисунке:

Пронумеруем вершины исходного графа, и составим матрицу длин кратчайших дуг между каждой парой вершин D⁰, в случае, если дуги между вершиной i и j не существует, элементу a_i,j матрицы присваивается значение ∞. Исходный граф с пронумероваными вершинами представлен на рисунке ниже.

Матрица D⁰:

C помощью алгоритма Флойда или Данцега получаем матрицу длин кратчайших путей между каждой парой вершин графа:

Используя полученные нами матрицы D⁰ и D⁷расчитаем элементы матрицы D’. Элементами матрицы D’ являются расстояния вершина-дуга (ВД). Для расчета расстояний вершина-дуга используем соотношения:

d'(j, (r, s))= (d_{j, r}+ d_{j, s} +a_{r, s})/2, – для неориентированой дуги

d'(j, (r, s))= d_{j, r}+ a_{r, s}, – для ориентированой дуги

Ниже приведены расчеты первой строки таблицы D’ (расчитаны расстояния вершина-дуга для вершины №1):
d'(1, (1, 2))= (d_{1, 1}+d_{1, 2}+a_{1, 2})/2=12
d'(1, (1, 4))= (d_{1, 1}+d_{1, 4}+a_{1, 4})/2=28
d'(1, (2, 3))= (d_{1, 2}+d_{1, 3}+a_{2, 3})/2=22
d'(1, (2, 4))= (d_{1, 2}+d_{1, 4}+a_{2, 4})/2=41.5
d'(1, (3, 5))= (d_{1, 3}+d_{1, 5}+a_{3, 5})/2=32
d'(1, (4, 3))= d_{1, 4}+a_{4, 3}=45
d'(1, (5, 2))= d_{1, 5}+a_{5, 2}=63
d'(1, (5, 6))= d_{1, 5}+a_{5, 6}=40
d'(1, (6, 5))= d_{1, 6}+a_{6, 5}=54
d'(1, (6, 7))= (d_{1, 6}+d_{1, 7}+a_{6, 7})/2=46
Полностью расчитаная матрица D’:

Расчитаем сумму элементов для каждой строки и выберем из них минимальную:
CВД(1)=383.5
CВД(2)=335.5
CВД(3)=325.5
CВД(4)=350.5
CВД(5)=335.5
CВД(6)=431.5
CВД(7)=485.5
Минимальное значение имеет CВД(3)=325.5, а это значит, что вершина 3 является главной медианой графа.