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

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

4.5 Диаметр, радиус и центр графа

 

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

 

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

 

 

24