logo
Лекции ДМ

2. Метрические характеристики неориентированного графа

Пусть G(V,X) – псевдограф и пусть вершины v и w (vw) данного графа можно соединить маршрутом. Тогда обязательно существует и минимальный маршрут, соединяющий эти вершины. Обозначим длину этого маршрута d(v, w). Положим также d(v, v) =0 для любой вершины vV; d(v, w) = , если не существует маршрута, соединяющего v и w.

Определенная таким образом величина d(v,w) для любых вершин v и w графа G(V, X) называется расстоянием между v и w.

Число расстояний в графе с n вершинами равно числу сочетаний Cn2 .

Пусть граф G(V,X) связный. Определим для него следующие понятия:

Диаметр графа: d(G) = maxd(v, w).

v, wV

Эксцентриситет (максимальное удаление) вершины: r(v) = maxd(v, w);

vV

Радиус графа : r(G) = min r(v);

vV

Центр графа: любая вершина vV,такая, что r(v) = r(G).

Диаметр графа, эксцентриситеты вершин , радиус графа и центры графа называются метрическими характеристиками графа.

Пример. Найти метрические характеристики графа, заданного диаграммой:

Найдем все расстояния, учитывая, что d(v, w) = d(w, v).

Число расстояний в данном графе С52 = 5!/3!2! = 10: d(v1, v2) =1, d(v1, v3) = 2, d(v1, v4) = 2, d(v1, v5) = 3, d(v2, v3) = 1, d(v2, v4) = 1, d(v2, v5) = 2, d(v3, v4) = 1, d(v3, v5) = 2, d(v4, v5) = 1.

Диаметр графа d(G) =3.

Эксцентриситеты вершин: r(v1) = 3, r(v2) = 2, r(v3) = 2, r(v4) = 2, r(v5) = 3.

Радиус графа r(G) = 2.

Центры графа v2, v3, v4 .

  1.