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

Необходимо определить абсолютный центр для графа:
Составим матрицу длин кратчайших дуг между каждой парой вершин D⁰, в случае, если дуги между вершиной i и j не существует, элементу d_i,j матрицы присваивается значение ∞.

Матрица D⁰:

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

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

МВВ(i)=max{d_i,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+d_r,j, (1—f)×а_{r, s}+d_s,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.