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

Медиана графа – такая вершина x, суммарное расстояние от которой до всех остальных вершин графа минимально.Cуммарное расстояние от вершины до всех остальных вершин – СВВ(i) определяется соотношением СВВ(i)= Σd_i,j  – суммарное расстояние от вершины i до всех j.

СВВ(x)=min {СВВ(i)}

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

• • находим D⁰ – матрица, элементами которой являются a_i,j – длины кратчайших дуг;
  • Ищем  D^N –  матрицу длин кратчайших путей между всеми вершинами графа по Флойду или Данцигу;
  • Определяем  СВВ(i);
  • Из всех СВВ(i) выбираем наименьшее, соответствующая вершина и будет медианой;

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

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

Матрица D⁰:

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

Основываясь на полученой нами матрице длин кратчайших путей, найдем CВВ(i) для каждой вершины графа

CВВ(i)=Σd_i,j.

CВВ(1)==Σ_jd(1, j)=180
CВВ(2)==Σ_jd(2, j)=144
CВВ(3)==Σ_jd(3, j)=134
CВВ(4)==Σ_jd(4, j)=175
CВВ(5)==Σ_jd(5, j)=144
CВВ(6)==Σ_jd(6, j)=198
CВВ(7)==Σ_jd(7, j)=228
Медианой графа является такая вершина x, для которой СВВ(x)=min{СВВ(i)}. Минимальное значение имеет СВВ(3)=134, а это значит, что вершина 3 является медианой графа.