yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->4.6 Параметры протяженности (диаметр, радиус и центр) графа

Дискретная математика

4.6 Параметры протяженности (диаметр, радиус и центр) графа

 

Задан единичный связный неориентированный граф 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.

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

 

 

25