Главная|Решения онлайн |Теория | Основные формулы и обозначения |Обратная связь |

Центр графа

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

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

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

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

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

Пример

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

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

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{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 является центром графа.

Назад