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

МВВ(х) =min{МВВ(i)}

Центр отыскивается как один из элементов матрицы DN, значение i, j-го элемента которой — di,j есть кратчайшее расстояние от вершины i к вершине j. Элементы матрицы могут быть вычислены с помощью алгоритма Флойда или алгоритма Данцига. Максимальное расстояние МВВ(i) от вершины i до любой вершины графа является элементом i-й строки матрицы DN, имеющим максимальное значение. Центром является произвольная вершина х с наименьшим среди всех вершин графа звачеявем МВВ(х), т. е. центр — это произвольная вершина х, которой соответствует строка матрицы DN, содержащая элемент с наименьшим максимальным значением.
Алгоритм поиска центра

    1. находим D0 – матрицу, элементами которой являются ai,j – длины кратчайших дуг.
    2. Ищем   DN –  матрицу длин кратчайших расстояний по Флойду или Данцегу.
    3. Определяем  МВВ(i) для каждой вершины графа.
    4. Из всех МВВ(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 является центром графа.

   
4.95
user372112
Специализируюсь на курсовых работах, контрольных, рефератах по множеству дисциплин. Владею английским на уровне C1, ежедневно общаюсь с носителями языка. Самостоятельно пишу грамотные работы с высоким уровнем оригинальности. Обращайтесь!

Найдем готовую работу в нашей базе