Задан единичный связный неориентированный граф G. Максимальная длина простой цепи с началом V' и концом V" называется протяженностью между этими вершинами g(V',V").
Диаметр протяженности графа - максимальная из протяженностей между любыми парами вершин:
L(G) = max g(V',V").
(V",V') c G
Для каждой вершины V существуют самые длинные простые цепи связывающие ее с другими вершинами графа; их длина называется, числом протяжённости для вершин l(V) = max g(V(i)).
V(i) c G
Центры протяжённости - вершины с минимальным числом протяженности.
l(G) = min l(V)
V c 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 ¦l(V)¦центр¦
+----г==+==+==+==+==+==¬----+-----+
¦ a ¦ 0¦ 2¦ 2¦ 4¦ 4¦ 5¦ 5 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ b ¦ 2¦ 0¦ 2¦ 4¦ 4¦ 5¦ 5 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ c ¦ 2¦ 2¦ 0¦ 2¦ 2¦ 3¦ 3 ¦ v ¦
+----+--+--+--+--+--+--+----+-----+
¦ d ¦ 4¦ 4¦ 2¦ 0¦ 2¦ 3¦ 4 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ e ¦ 4¦ 4¦ 2¦ 2¦ 0¦ 3¦ 4 ¦ ¦
+----+--+--+--+--+--+--+----+-----+
¦ f ¦ 5¦ 5¦ 3¦ 3¦ 3¦ 0¦ 5 ¦ ¦
L----L==¦==¦==¦==¦==¦==-----+------
В столбце с заголовком l(V) укажем числа протяженностей отсоответствующих вершин (максимальное значение протяженностей каждой строки). Максимальное из чисел протяженностей и будет диаметром протяженности графа(т.е. максимально возможной протяженностью между вершинами в исследуемом графе): L(G) = 5.
Вершина с, для которых удаление l(V) принимает минимальное значение (помечена v ), являются центром протяженности графа G, азначение числа протяженности - радиусом протяженности графа:l(G) = 3.
Если ребра графа нагружены (каждому ребру поставлено в соот-ветствие определенное числовое значение), то процедура исследования аналогична описанной выше, но при заполнении матрицы нужно определять протяженность между вершинами не по числу ребер, а по суммарной их длине.
Тема №4. Теория конечных автоматов.