Задан единичный связный неориентированный граф G.
Минимальная длина простой цепи с началом V' и концом V" называется расстоянием между этими вершинами d(V',V").
Диаметр графа - максимальное из расстояний между любыми парами вершин:
D(G) = max d(V',V").
(V",V') c G
Если принять за точку отсчёта расстояний одну из вершин графа(например V),то максимальное из расстояний от V до любой из вершин графа G называется максимальным удалением:
r(V) = max d(V(i)).
V(i) c G
Вершина V называется центром графа, если максимальное удаление от неё принимает минимальное значение. Максимальное удаление от центра называется радиусом графа.
r(G) = min r(V)
V c G
Любая простая цепь от центра V до максимально удаленной от него вершины называется радиальной цепью.
Рассмотрим на примере определение этих параметров графа (анализ графа на минимум).
Задан единичный неориентированный граф G:
V={a,b,c,d,e,f}; E={ab,ac,bc,cd,ce,de,ef}. Определить диаметр, центр(центры) и радиус этого графа.
Для определения этих параметров изобразим граф G и составим матрицу расстояний: (на пересечении столбца и строки (вершины графа) матрицы указывается расстояние между этими вершинами; такая матрица (выделена на рисунке) симметрична относительно главной диагонали).
-----T--T--T--T--T--T--T----T-----¬
¦ ¦a ¦b ¦c ¦d ¦e ¦f ¦r(V)¦центр¦
+----г==+==+==+==+==+==¬----+-----+
¦ a ¦ 0¦ 1¦ 1¦ 2¦ 2¦ 3¦ 3 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ b ¦ 1¦ 0¦ 1¦ 2¦ 2¦ 3¦ 3 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ c ¦ 1¦ 1¦ 0¦ 1¦ 1¦ 2¦ 2 ¦ v ¦
+----+--+--+--+--+--+--+----+-----+
¦ d ¦ 2¦ 2¦ 1¦ 0¦ 1¦ 2¦ 2 ¦ v ¦
+----+--+--+--+--+--+--+----+-----+
¦ e ¦ 2¦ 2¦ 1¦ 1¦ 0¦ 1¦ 2 ¦ v ¦
+----+--+--+--+--+--+--+----+-----+
¦ f ¦ 3¦ 3¦ 2¦ 2¦ 1¦ 0¦ 3 ¦ ¦
L----L==¦==¦==¦==¦==¦==-----+------
В столбце с заголовком r(V) укажем удаления от соответствующих вершин (максимальное значение расстояния каждой строки). Максимальное из удалений и будет диаметром графа(т.е. максимально возможным расстоянием между вершинами в исследуемом графе):D(G) = 3.
Вершины, для которых удаление r(V) принимает минимальное значение (помечены v ), являются центрами графа G, а значение удаления - радиусом графа: r(G) = 2.
Если ребра графа нагружены (каждому ребру поставлено в соответствие определенное числовое значение), то процедура исследования аналогична описанной выше, но при заполнении матрицы нужно определять расстояние между вершинами не по числу ребер, а по суммарной их длине.