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

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

СВД (х) = 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. находим D – матрица, элементами которой являются ai,j – длины кратчайших дуг.
    2. расчитываем DN –  матрицу длин кратчайших путей между всеми вершинами графа по Флойду или Данцигу.
    3. определяем элементы матрицы D’ (матрица, элементами которой являются расстояния вершина-дуга)
    4. Находим СВД(i) для каждой вершины графа
    5. Выбираем минимальное СВД(i) из найденых нами — соответствующая вершина является главной медианой графа.
Читайте также  Алгоритм Литтла - Пример 1

Пример

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

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

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

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

Матрица D:

D= 12 28
12 10 43
10 10
28 43 17
31 10 8
14 6
6

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

D7= 12 22 28 32 40 46
12 10 40 20 28 34
22 10 50 10 18 24
28 27 17 27 35 41
32 20 10 60 8 14
46 34 24 74 14 6
52 40 30 80 20 6
Читайте также  Метод искусственного базиса (Симплекс метод) - Пример 2

Используя полученные нами матрицы 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)
1 12 28 22 41.5 32 45 63 40 54 46
2 12 40 10 41.5 20 57 51 28 42 34
3 22 50 10 51.5 10 67 41 18 32 24
4 33.5 28 27 35 27 17 58 35 49 41
5 32 60 20 61.5 10 77 31 8 22 14
6 46 74 34 75.5 24 91 45 22 14 6
7 52 80 40 81.5 30 97 51 28 20 6

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

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

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...