Центр графа

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

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

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

Читайте также  Абсолютный центр

Алгоритм поиска центра

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

Пример

Необходимо найти центр графа представленого на рисунке:

граф, центр которого необходимо найти

Составим матрицу длин кратчайших дуг между каждой парой вершин — D, в случае, если дуги между вершиной i и j не существует, элементу ai,j матрицы присваивается значение ∞. Матрица D:

D0= 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 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...