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