Пример — Абсолютный центр

Необходимо определить абсолютный центр для графа:
Составим матрицу длин кратчайших дуг между каждой парой вершин D, в случае, если дуги между вершиной i и j не существует, элементу di,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

Найдем абсолютный центр для графа. Мы знаем, что все абсолютные центры должны быть либо вершинами, либо внутренними точками на неориентированых дугах. Найдем сначала наилучшего претендента на роль абсолютного цекнтра среди вершин графа (то есть нам необходимо найти вершину, являющуюся центром графа. Основываясь на полученой нами матрице длин кратчайших путей, найдем МВВ(i) (минимальное расстояние Вершина-вершина) для каждой вершины графа

МВВ(i)=max{di,j}.

МВВ(1)=max{d(1, j)}=152
МВВ(2)=max{d(2, j)}=122
МВВ(3)=max{d(3, j)}=145
МВВ(4)=max{d(4, j)}=133
МВВ(5)=max{d(5, j)}=197
МВВ(6)=max{d(6, j)}=197
МВВ(7)=max{d(7, j)}=104
МВВ(8)=max{d(8, j)}=200
Центром графа является такая вершина x, для которой МВВ(x)=min{МВВ(i)}..
Минимальное значение имеет МВВ(7)=104, а это значит, что вершина 7 является центром графа и наилучшим претендентом на роль абсолютного центра графа среди вершин.

Читайте также  Алгоритмы поиска кратчайших путей

Теперь исследуем внутренние точки неориентированых дуг: (1,2), (1,5), (3,6), (4,8), . Для нахождения наилучшего претендента на роль абсолютного центра среди внутренних точек графа нам необходимо из множества точек названых дуг (ребер) найти такую точку f-(r,s), что

МТВ(f-(r,s))= min {МТВ(f-(t, u))}.

Исследуем ребро (1,2)

На основании уравнения d(f—(r,s ), j)=min{f×аr,s+dr,j, (1—f)×аr, s+ds,j} получим функции точка-вершина для каждой вершины графа:

d(f-(1, 2), 2)= min{fa(1, 2)+d(1, 2), (1-f)a(1, 2)+d(2, 2)}= min{67f+30, 67(1-f)+0}=-67f+67 для всех f;

d(f-(1, 2), 3)= min{fa(1, 2)+d(1, 3), (1-f)a(1,2)+d(2, 3)}= min{67f+70, 67(1-f)+40}=-67f+107 для всех f;

d(f-(1, 2), 4)= min{fa(1, 2)+d(1, 4), (1-f)a(1, 2)+d(2, 4)}= min{67f+47, 67(1-f)+17}=-67f+84 для всех f;

d(f-(1, 2), 5)= min{fa(1, 2)+d(1, 5), (1-f)a(1, 2)+d(2, 5)}= min{67f+45, 67(1-f)+75}=67f+45 для всех f;

d(f-(1, 2), 6)= min{fa(1, 2)+d(1, 6), (1-f)a(1, 2)+d(2, 6)}= min{67f+85, 67(1-f)+92}=67f+85 для f≤0.617 или -67f+159 для f≥0.617;

d(f-(1, 2), 7)= min{fa(1, 2)+d(1, 7), (1-f)a(1, 2)+d(2, 7)}= min{67f+152, 67(1-f)+122}=-67f+189 для всех f;

d(f-(1, 2), 8)= min{fa(1, 2)+d(1, 8), (1-f)a(1, 2)+d(2, 8)}= min{67f+23, 67(1-f)+53}=67f+23 для всех f.

Функции, характеризующие расстояния точка-вершина изображены на рисунке. Нам необходимо определить аргумент функции в точке, где верхняя граница имеет минимальное значение.

расстояния точка-вершина

В нашем случае это конечная точка ребра (1,2) — вершина №2 минимальное расстояние до наиболее удаленной вершины 7 от вершины 2 составляет d=122.

Читайте также  Табличный симплекс-метод

Исследуем ребро (1,5)

d(f-(1, 5), 1)= min{fa(1, 5)+d(1, 1), (1-f)a(1, 5)+d(5, 1)}= min{67f+0, 67(1-f)+45}=
67f+0 для всех f;

d(f-(1, 5), 2)=min{fa(1, 5)+d(1, 2), (1-f)a(1, 5)+d(5, 2)}= min{67f+30, 67(1-f)+75}=
67f+30 для всех f;

d(f-(1, 5), 3)= min{fa(1, 5)+d(1, 3), (1-f)a(1, 5)+d(5, 3)}= min{67f+70, 67(1-f)+92}=
67f+70 для f≤0.744
-67f+159 для f≥0.744;

d(f-(1, 5), 4)=min{fa(1, 5)+d(1, 4), (1-f)a(1, 5)+d(5, 4)}= min{67f+47, 67(1-f)+92}=
67f+47 для всех f ;

d(f-(1, 5), 5)= min{fa(1, 5)+d(1, 5), (1-f)a(1, 5)+d(5, 5)}= min{67f+45, 67(1-f)+0}=
-67f+67 для всех f;

d(f-(1, 5), 6)= min{fa(1, 5)+d(1, 6), (1-f)a(1, 5)+d(5, 6)}= min{67f+85, 67(1-f)+40}=
-67f+107 для всех f;

d(f-(1, 5), 7)= min{fa(1, 5)+d(1, 7), (1-f)a(1, 5)+d(5, 7)}= min{67f+152, 67(1-f)+197}=
67f+152 для всех f;

d(f-(1, 5), 8)= min{fa(1, 5)+d(1, 8), (1-f)a(1, 5)+d(5, 8)}= min{67f+23, 67(1-f)+68}=
67f+23 для всех f.

Функции, характеризующие расстояния точка-вершина изображены на рисунке

расстояния точка-вершина

Наилучшим претендентом для размещения абсолютного центра на дуге (1, 5) является вершина 1 d=152

Исследуем ребро (3,6)

d(f-(3, 6), 1)= min{fa(3, 6)+d(3, 1), (1-f)a(3, 6)+d(6, 1)}= min{67f+53, 67(1-f)+88}=67f+53 для f≤0.837 или -67f+155 для f≥0.837

d(f-(3,6), 2)= min{fa(3,6)+d(3, 2), (1-f)a(3,6)+d(6, 2)}= min{67f+23, 67(1-f)+75}=67f+23 для всех f

d(f-(3,6), 3)= min{fa(3,6)+d(3, 3), (1-f)a(3,6)+d(6, 3)}= min{67f+0, 67(1-f)+52}=67f+0 для всех f

d(f-(3,6), 4)= min{fa(3,6)+d(3, 4), (1-f)a(3,6)+d(6, 4)}= min{67f+12, 67(1-f)+64}=67f+12 для всех f

d(f-(3,6), 5)= min{fa(3,6)+d(3, 5), (1-f)a(3,6)+d(6, 5)}= min{67f+95, 67(1-f)+43}=-67f+110 для всех f

d(f-(3,6), 6)= min{fa(3,6)+d(3, 6), (1-f)a(3,6)+d(6, 6)}= min{67f+52, 67(1-f)+0}=-67f+67 для всех f

Читайте также  Задачи размещения

d(f-(3,6), 7)= min{fa(3,6)+d(3, 7), (1-f)a(3,6)+d(6, 7)}= min{67f+145, 67(1-f)+197}=67f+145 для всех f

d(f-(3,6), 8)= min{fa(3,6)+d(3, 8), (1-f)a(3,6)+d(6, 8)}= min{67f+76, 67(1-f)+111}=67f+76 для f<=0.837 или -67f+178для f≥0.837

Функции, характеризующие расстояния точка-вершина изображены на рисунке

расстояния точка-вершина

Наилучшим претендентом для размещения абсолютного центра на дуге (3, 6) является вершина 3 d=145

Исследуем ребро (4,8)

d(f-(4,8), 1)= min{fa(4,8)+d(4, 1), (1-f)a(4,8)+d(8, 1)}= min{67f+41, 67(1-f)+108}=67f+41 для всех f;

d(f-(4,8), 2)= min{fa(4,8)+d(4, 2), (1-f)a(4,8)+d(8, 2)}= min{67f+11, 67(1-f)+78}=67f+11 для всех f

d(f-(4,8), 3)= min{fa(4,8)+d(4, 3), (1-f)a(4,8)+d(8, 3)}= min{67f+23, 67(1-f)+90}=67f+23 для всех f;

d(f-(4,8), 4)= min{fa(4,8)+d(4, 4), (1-f)a(4,8)+d(8, 4)}= min{67f+0, 67(1-f)+67}=67f+0 для всех f;

d(f-(4,8), 5)= min{fa(4,8)+d(4, 5), (1-f)a(4,8)+d(8, 5)}= min{67f+86, 67(1-f)+153}=67f+86 для всех f;

d(f-(4,8), 6)= min{fa(4,8)+d(4, 6), (1-f)a(4,8)+d(8, 6)}= min{67f+75, 67(1-f)+142}=67f+75 для всех аж

d(f-(4,8), 7)= min{fa(4,8)+d(4, 7), (1-f)a(4,8)+d(8, 7)}= min{67f+133, 67(1-f)+200}= 67f+133 для всех f

d(f-(4,8), 8)= min{fa(4,8)+d(4, 8), (1-f)a(4,8)+d(8, 8)}= min{67f+64, 67(1-f)+0}=67f+64 для f≤0.0224 или —67f+67 для f≥0.0224

Функции, характеризующие расстояния точка-вершина изображены на рисунке

расстояния точка-вершина

Наилучшим претендентом для размещения абсолютного центра на дуге (4, 8) является вершина 4 d=133

Теперь выберем оптимальный вариант из всех претендентов. Критерием является расстояние до наиболее удаленной точки графа которое должно быть минимально.
Абсолютным центром графа является вершина 7 которая так же является и центром графа, расстояние от нее до наиболее удаленной точки графа равно 104.

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