Метрические характеристики графа

Пусть G = (S, U) – связный граф и x_i, x_j – две его произвольные вершины.

Определение 9.1. Расстоянием d (x_i, x_j) между вершинами x_i и x_j называется длина кратчайшего маршрута, соединяющего эти вершины.

Из определения 9.1 непосредственно следует:

1) кратчайший маршрут между вершинами является простой цепью;

2) d (x_i, x_i) =0.

Определение 9.2. Эксцентриситетом вершины x называется величина

e(x) = (9.1)

Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удалëнной от неë.

Определение 9.3. Диаметром d (G) графа G называется максимальный из всех эксцентриситетов вершин графа G, т.е.

d (G) = (9.2)

Определение 9.4. Вершина x называется периферийной, если e (x) = d (G).

Определение 9.5. Диаметральной цепью называется простая цепь, расстояние между концами которой равно d (G).

Теорема 9.1. Для любого связного графа G справедливо неравенство

d (G) £ rank G. 

Определение 9.6. Радиусом r (G) графа G называется минимальный из всех эксцентриситетов вершин графа G, т.е.

r (G) = (9.3)

Определение 9.7. Вершина x называется центральной, если e (x) = r (G).

Определение 9.8. Множество всех центральных вершин графа называется его центром.

Заметим, что центр может состоять как из одной, так и из нескольких вершин.

Пример 9.1. Найти эксцентриситеты вершин, радиусы и диаметры графа G, изображëнного на рис. 16, периферийные и центральные вершины. Привести

пример диаметральной цепи.

Решение. Найдëм эксцентриситеты всех вершин G: e (x₁) = e (x₄) = e (x₅) = 4,

e (x₂) = e (x₆) = e (x₇) = e (x₈) = 3, e (x₃) = 2.

Следовательно, d (G) = 4, r (G) = 2. Получаем, что вершины x₁, x₄ и x₅ являются периферийными, а вершина x₃ – центральной. Одной из диаметральных цепей является

x₁ – x₇ – x₃ – x₆ – x₅.