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


Главный центр

Главный центр — это произвольная вершина х с минимальным среди всех вершин значением МВД(х) -максимальное расстояние вершина-дуга, т. е. главным центром является такая вершина х, что расстояние от х до наиболее удаленной точки на дугах графа минимально.

МВД(x)=min{МВД(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) неориентированная.

Для расчета элементов матрицы расстояний вершина-дуга D' нам (как видно из соотношений для расчета) понадобятся матрицы D0- матрица длин кратчайших дуг графа, и матрица DN - матрица длин кратчайших путей, которую можно получить с помощью алгоритма Флойда или Данцига. Представим теперь алгоритм поиска главного центра.

Алгоритм поиска главного центра

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

Пример

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

определить главный центр для графа

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

Матрица D0:

D8= 0 30 45 23
30 0 17 122
34 0 12 52
11 23 0 67
45 0 40
52 43 0
12 0
67 0

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

D8= 0 30 70 47 45 85 152 23
30 0 40 17 75 92 122 53
53 23 0 12 95 52 145 76
41 11 23 0 86 75 133 64
45 75 92 92 0 40 197 68
88 75 52 64 43 0 197 111
42 12 52 29 87 104 0 65
108 78 90 67 153 142 200 0


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

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

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

d'(1, (1, 2))= (d1, 1+d1, 2+a1, 2)/2=30
d'(1, (1, 5))= (d1, 1+d1, 5+a1, 5)/2=45
d'(1, (1, 8))= d1, 1+a1, 8=23
d'(1, (2, 4))= d1, 2+a2, 4=47
d'(1, (2, 7))= d1, 2+a2, 7=152
d'(1, (3, 2))= d1, 3+a3, 2=104
d'(1, (3, 4))= d1, 3+a3, 4=82
d'(1, (3, 6))= (d1, 3+d1, 6+a3, 6)/2=103.5
d'(1, (4, 2))= d1, 4+a4, 2=58
d'(1, (4, 3))= d1, 4+a4, 3=70
d'(1, (4, 8))= (d1, 4+d1, 8+a4, 8)/2=68.5
d'(1, (5, 6))= d1, 5+a5, 6=85
d'(1, (6, 5))= d1, 6+a6, 5=128
d'(1, (7, 2))= d1, 7+a7, 2=164
d'(2, (1, 2))= (d2, 1+d2, 2+a1, 2)/2=30
d'(2, (1, 5))= (d2, 1+d2, 5+a1, 5)/2=75
d'(2, (1, 8))= d2, 1+a1, 8=53
d'(2, (2, 4))= d2, 2+a2, 4=17
d'(2, (2, 7))= d2, 2+a2, 7=122
d'(2, (3, 2))= d2, 3+a3, 2=74
d'(2, (3, 4))= d2, 3+a3, 4=52
d'(2, (3, 6))= (d2, 3+d2, 6+a3, 6)/2=92
d'(2, (4, 2))= d2, 4+a4, 2=28
d'(2, (4, 3))= d2, 4+a4, 3=40
d'(2, (4, 8))= (d2, 4+d2, 8+a4, 8)/2=68.5
d'(2, (5, 6))= d2, 5+a5, 6=115
d'(2, (6, 5))= d2, 6+a6, 5=135
d'(2, (7, 2))= d2, 7+a7, 2=134
d'(3, (1, 2))= (d3, 1+d3, 2+a1, 2)/2=53
d'(3, (1, 5))= (d3, 1+d3, 5+a1, 5)/2=96.5
d'(3, (1, 8))= d3, 1+a1, 8=76
d'(3, (2, 4))= d3, 2+a2, 4=40
d'(3, (2, 7))= d3, 2+a2, 7=145
d'(3, (3, 2))= d3, 3+a3, 2=34
d'(3, (3, 4))= d3, 3+a3, 4=12
d'(3, (3, 6))= (d3, 3+d3, 6+a3, 6)/2=52
d'(3, (4, 2))= d3, 4+a4, 2=23
d'(3, (4, 3))= d3, 4+a4, 3=35
d'(3, (4, 8))= (d3, 4+d3, 8+a4, 8)/2=77.5
d'(3, (5, 6))= d3, 5+a5, 6=135
d'(3, (6, 5))= d3, 6+a6, 5=95
d'(3, (7, 2))= d3, 7+a7, 2=157
d'(4, (1, 2))= (d4, 1+d4, 2+a1, 2)/2=41
d'(4, (1, 5))= (d4, 1+d4, 5+a1, 5)/2=86
d'(4, (1, 8))= d4, 1+a1, 8=64
d'(4, (2, 4))= d4, 2+a2, 4=28
d'(4, (2, 7))= d4, 2+a2, 7=133
d'(4, (3, 2))= d4, 3+a3, 2=57
d'(4, (3, 4))= d4, 3+a3, 4=35
d'(4, (3, 6))= (d4, 3+d4, 6+a3, 6)/2=75
d'(4, (4, 2))= d4, 4+a4, 2=11
d'(4, (4, 3))= d4, 4+a4, 3=23
d'(4, (4, 8))= (d4, 4+d4, 8+a4, 8)/2=65.5
d'(4, (5, 6))= d4, 5+a5, 6=126
d'(4, (6, 5))= d4, 6+a6, 5=118
d'(4, (7, 2))= d4, 7+a7, 2=145
d'(5, (1, 2))= (d5, 1+d5, 2+a1, 2)/2=75
d'(5, (1, 5))= (d5, 1+d5, 5+a1, 5)/2=45
d'(5, (1, 8))= d5, 1+a1, 8=68
d'(5, (2, 4))= d5, 2+a2, 4=92
d'(5, (2, 7))= d5, 2+a2, 7=197
d'(5, (3, 2))= d5, 3+a3, 2=126
d'(5, (3, 4))= d5, 3+a3, 4=104
d'(5, (3, 6))= (d5, 3+d5, 6+a3, 6)/2=92
d'(5, (4, 2))= d5, 4+a4, 2=103
d'(5, (4, 3))= d5, 4+a4, 3=115
d'(5, (4, 8))= (d5, 4+d5, 8+a4, 8)/2=113.5
d'(5, (5, 6))= d5, 5+a5, 6=40
d'(5, (6, 5))= d5, 6+a6, 5=83
d'(5, (7, 2))= d5, 7+a7, 2=209
d'(6, (1, 2))= (d6, 1+d6, 2+a1, 2)/2=96.5
d'(6, (1, 5))= (d6, 1+d6, 5+a1, 5)/2=88
d'(6, (1, 8))= d6, 1+a1, 8=111
d'(6, (2, 4))= d6, 2+a2, 4=92
d'(6, (2, 7))= d6, 2+a2, 7=197
d'(6, (3, 2))= d6, 3+a3, 2=86
d'(6, (3, 4))= d6, 3+a3, 4=64
d'(6, (3, 6))= (d6, 3+d6, 6+a3, 6)/2=52
d'(6, (4, 2))= d6, 4+a4, 2=75
d'(6, (4, 3))= d6, 4+a4, 3=87
d'(6, (4, 8))= (d6, 4+d6, 8+a4, 8)/2=121
d'(6, (5, 6))= d6, 5+a5, 6=83
d'(6, (6, 5))= d6, 6+a6, 5=43
d'(6, (7, 2))= d6, 7+a7, 2=209
d'(7, (1, 2))= (d7, 1+d7, 2+a1, 2)/2=42
d'(7, (1, 5))= (d7, 1+d7, 5+a1, 5)/2=87
d'(7, (1, 8))= d7, 1+a1, 8=65
d'(7, (2, 4))= d7, 2+a2, 4=29
d'(7, (2, 7))= d7, 2+a2, 7=134
d'(7, (3, 2))= d7, 3+a3, 2=86
d'(7, (3, 4))= d7, 3+a3, 4=64
d'(7, (3, 6))= (d7, 3+d7, 6+a3, 6)/2=104
d'(7, (4, 2))= d7, 4+a4, 2=40
d'(7, (4, 3))= d7, 4+a4, 3=52
d'(7, (4, 8))= (d7, 4+d7, 8+a4, 8)/2=80.5
d'(7, (5, 6))= d7, 5+a5, 6=127
d'(7, (6, 5))= d7, 6+a6, 5=147
d'(7, (7, 2))= d7, 7+a7, 2=12
d'(8, (1, 2))= (d8, 1+d8, 2+a1, 2)/2=108
d'(8, (1, 5))= (d8, 1+d8, 5+a1, 5)/2=153
d'(8, (1, 8))= d8, 1+a1, 8=131
d'(8, (2, 4))= d8, 2+a2, 4=95
d'(8, (2, 7))= d8, 2+a2, 7=200
d'(8, (3, 2))= d8, 3+a3, 2=124
d'(8, (3, 4))= d8, 3+a3, 4=102
d'(8, (3, 6))= (d8, 3+d8, 6+a3, 6)/2=142
d'(8, (4, 2))= d8, 4+a4, 2=78
d'(8, (4, 3))= d8, 4+a4, 3=90
d'(8, (4, 8))= (d8, 4+d8, 8+a4, 8)/2=67
d'(8, (5, 6))= d8, 5+a5, 6=193
d'(8, (6, 5))= d8, 6+a6, 5=185
d'(8, (7, 2))= d8, 7+a7, 2=212

D'= (1,2) (1,5) (1,8) (2,4) (2,7) (3,2) (3,4) (3,6) (4,2) (4,3) (4,8) (5,6) (6,5) (7,2)
1 30 45 23 47 152 104 82 103.5 58 70 68.5 85 128 164
2 30 75 53 17 122 74 52 92 28 40 68.5 115 135 134
3 53 96.5 76 40 145 34 12 52 23 35 77.5 135 95 157
4 41 86 64 28 133 57 35 75 11 23 65.5 126 118 145
5 75 45 68 92 197 126 104 92 103 115 113.5 40 83 209
6 96.5 88 111 92 197 86 64 52 75 87 121 83 43 209
7 42 87 65 29 134 86 64 104 40 52 80.5 127 147 12
8 108 153 131 95 200 124 102 142 78 90 67 193 185 212

Определим максимальное значение в каждой строке:
МВД(1)=164
МВД(2)=135
МВД(3)=157
МВД(4)=145
МВД(5)=209
МВД(6)=209
МВД(7)=147
МВД(8)=212
Минимальное значение имеет МВД(2)=135, а это значит, что вершина 2 является главным центром графа.

Назад



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