Задача 12

Взвешенный граф задан матрицей весов. Построить его графическое представление, с помощью алгоритма Дейкстры определить матрицу расстояний. Найти радиус, центр и диаметр графа.

Изобразим данный граф:

Над каждым ребром подпишем его вес

Определим матрицу расстояний для данного графа:

		0+1=1	0+2=2	0+2+3=5	0+2+2=4	0+2=2
	0+2=2		0+2+2=4	0+2+3=5	0+2+3=5	0+1=1
	0+2=2	0+2+2=4		0+3=3	0+3+3=6	0+2+2=4
	0+3+2=5	0+3+2=5	0+3=3		0+3=3	0+3+2+1=6
	0+2+2=4	0+2+3=5	0+3+3=6	0+3=3		0+2+1=3
	0+2=2	0+1=1	0+2+2=4	0+3+2+1=6	0+2+1=3

Определим для каждой вершины графа наибольшее удаление:

, , , , ,

Минимальное из полученных чисел является радиусом графа, а максимальное – диаметром:

,

Центрами являются вершины и

Заказать контрольную работу по дискретной математике и не только Вы можете у нас на сайте http://otl.su

Также посетите нашу группу Вконтакте: http://vk.com/otlsu

OTL.SU – Быстро, качественно, доступно!

Дата добавления: 2015-10-13