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

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

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

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

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

Пример

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

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

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

Матрица D:

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

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

D8= 30 70 47 45 85 152 23
30 40 17 75 92 122 53
53 23 12 95 52 145 76
41 11 23 86 75 133 64
45 75 92 92 40 197 68
88 75 52 64 43 197 111
42 12 52 29 87 104 65
108 78 90 67 153 142 200
Читайте также  Теория графов

Теперь, основываясь на полученой нами матрице расстояний вершина-вершина D8 и исходной матрице длин кратчайших дуг D мы можем расчитать элементы матрицы 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 является главным центром графа.

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