На странице представлен фрагмент
Реши любую задачу с помощью нейросети.
Вспомним, что центром является любая вершина х с наименьшим значением МВВ(х) (макимальное расстояние вершина-вершина), т. е. центр — это любая вершина х, такая, что расстояние от нее до наиболее отдаленной вершины минимально.
МВВ(х) =min{МВВ(i)}
Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой — di,j есть кратчайшее расстояние от вершины i к вершине j. Элементы матрицы могут быть вычислены с помощью алгоритма Флойда или алгоритма Данцига. Максимальное расстояние МВВ(i) от вершины i до любой вершины графа является элементом i-й строки матрицы DN, имеющим максимальное значение. Центром является произвольная вершина х с наименьшим среди всех вершин графа звачеявем МВВ(х), т. е. центр — это произвольная вершина х, которой соответствует строка матрицы DN, содержащая элемент с наименьшим максимальным значением.
Алгоритм поиска центра
-
- находим D0 – матрицу, элементами которой являются ai,j – длины кратчайших дуг.
- Ищем DN – матрицу длин кратчайших расстояний по Флойду или Данцегу.
- Определяем МВВ(i) для каждой вершины графа.
- Из всех МВВ(i) выбираем минимальное соответствующая вершина и будет центром.
Пример
Необходимо найти центр графа представленого на рисунке:
Составим матрицу длин кратчайших дуг между каждой парой вершин – D0, в случае, если дуги между вершиной i и j не существует, элементу ai,j матрицы присваивается значение ∞. Матрица D0:
D0= | 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 является центром графа.