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


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

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

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

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

d'(j, (r, s))= dj,r+ dj,s +ar,s/2,

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

d'(j, (r, s))= dj,r+ ar,s,

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

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

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

Пример

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

найти главную медиану для графа

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

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

Матрица D0:

D0=01228
1201043
10010
2843170
311008
1406
60

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

D7=0122228324046
1201040202834
2210050101824
2827170273541
322010600814
463424741406
524030802060

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

d'(j, (r, s))= (dj, r+ dj, s +ar, s)/2, - для неориентированой дуги

d'(j, (r, s))= dj, r+ ar, s, - для ориентированой дуги

Ниже приведены расчеты первой строки таблицы D' (расчитаны расстояния вершина-дуга для вершины №1):

d'(1, (1, 2))= (d1, 1+d1, 2+a1, 2)/2=12
d'(1, (1, 4))= (d1, 1+d1, 4+a1, 4)/2=28
d'(1, (2, 3))= (d1, 2+d1, 3+a2, 3)/2=22
d'(1, (2, 4))= (d1, 2+d1, 4+a2, 4)/2=41.5
d'(1, (3, 5))= (d1, 3+d1, 5+a3, 5)/2=32
d'(1, (4, 3))= d1, 4+a4, 3=45
d'(1, (5, 2))= d1, 5+a5, 2=63
d'(1, (5, 6))= d1, 5+a5, 6=40
d'(1, (6, 5))= d1, 6+a6, 5=54
d'(1, (6, 7))= (d1, 6+d1, 7+a6, 7)/2=46

Полностью расчитаная матрица D':

D'=(1,2)(1,4)(2,3)(2,4)(3,5)(4,3)(5,2)(5,6)(6,5)(6,7)
112282241.5324563405446
212401041.5205751284234
322501051.5106741183224
433.5282735271758354941
532602061.510773182214
646743475.524914522146
752804081.530975128206

Расчитаем сумму элементов для каждой строки и выберем из них минимальную:

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 является главной медианой графа.

 

Назад



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