3.4. Нахождение диаметра, радиуса и центра графа

Определения.

Диаметров графа (взвешенного) называется максимально возможное расстояние между вершинами.

- максимальная стоимость маршрута u → v.

Радиусом графа называется минимально возможный радиус круга (центра круга выбирается среди всех вершин), внутри которого помещается весь граф.

где - минимально возможный радиус круга (в который входит весь граф) с центром в вершинеu.

Центр графа - та вершина u₀, для которой достигается минимально возможный радиус круга: u₀: r(u₀) = r(G).

При применении алгоритма Дейкстры и диаметр, и радиус графа можно найти за T = n·n² операция, где n² – трудоемкость однократного применения алгоритма Дейкстры.

Алгоритм Дейкстры мы запускаем n раз: с начала от v₀, потом от v₁ и т.д. перебирая все возможные вершины u. Получаем квадратную матрицу d(u,v) = n × n, по которой мы за n² операций находим диаметр и радиус графа.