На странице представлен фрагмент

Реши любую задачу с помощью нейросети.

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

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

   
4.97
Elena2008
Тесты на сайтах дистанционного обучения: ТОГУ, ТПУ, ТУСУР, система "Прометей","КОСМОС", i-exam и т.п. Выполняю контрольные и лабораторные работы по физико-математическим предметам.