Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |


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

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

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

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

Алгоритм поиска медианы.

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

Пример

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

граф для которого нужно найти медиану

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

граф с пронумерованными вершинами

Матрица D0:

D0= 0 12 28
12 0 10 43
10 0 10
28 43 17
0
31 10 0 8
14 0 6
6 0

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

D7= 0 12 22 28 32 40 46
12 0 10 40 20 28 34
22 10 0 50 10 18 24
28 27 17 0 27 35 41
32 20 10 60 0 8 14
46 34 24 74 14 0 6
52 40 30 80 20 6 0

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

CВВ(i)=Σdi,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 является медианой графа.

Назад



R336709263964 - WebMoney 41001419134483 - Яндекс Деньги
WebMoneyПонравился сайт? Окажите помощь в развитиияндекс