Характеристики расстояний в графах

Пусть G(X) – конечный или бесконечный ориенти­рованный граф. Отклонением d(x_i, x_j) его вершины x_i от вершины x_j называ­ется длина кратчайшего пути из х_i в x_j:

d(x_i, x_j) = min {l[S_k(x_i, x_j)]}.

Отклонение d(x_i, x_j) удовлетворяет следующим аксио­мам мет­рического пространства:

1. d(x_i, x_j) ³ 0;

2. d(x_i, x_j) = 0 Û x_i = x_j;

3. d(x_i, x_j) + d(x_j, x_k) ³ d(x_i, x_k) – неравенство треуголь­ника и не удовлетворяет четвертой аксиоме, а именно:

4. d(xi, xj) ¹ d(xj, xi), так как граф ориентирован.

Необходимо отметить, что если x_j Ï G(x_i), то d(x_i, x_j) = ¥. Отклоненностью вершины x_i называется наибольшее из от­клонений d(x_i, x_j) по всем x_j:

.

В качестве примера рассмотрим схему первой (1870 г.) сети связи для почтовых голубей (рис. 3.29).

Рис. 3.29. Схема первой сети связи для почтовых голубей

Граф, пред­став­ляющий ее, изображен на рис. 3.29, а матрица отклонений и вектор отклоненностей – в табл. 3.2 и табл. 3.3 соответственно.

Таблица 3.2. Отклонения d(x_i, x_j)

Таблица 3.3. Вектор отклонений

Для неориентированного графа, соответствующего графу, изо­браженному на рис. 3.29, можно найти аналогичные характеристики, но без учета ориентации дуг. При этом матрица d(x_i, x_j) оказывается симметричной.

В связном неориентированном графе понятиям отклонения и отклоненности соответствуют понятия: расстояние и удаленность.

Пусть G(X) – связный неориентированный граф. В соответст­вии с определением связности для вершин x_i и x_j графа существует элементарная цепь S(x_i, x_j) с концами x_i и x_j, причем l(S) ³ 0.

Расстоянием d(x_i, x_j) между вершинами x_i и x_j называется дли­на цепи S(x_i, x_j) наименьшей длины

.

Удаленность вершины x_i графа G(X) есть число

.

Центром графа называется вершина, в которой достигается наименьшая из отклоненностей (удаленностей), если таковая являет­ся конечным числом. В графе может быть несколько центров (Париж, Лион), а может не быть ни одного.

Периферийной вершиной графа называется вершина с наи­большей отклоненностью или удаленностью (Гренобль, Ницца).

Радиусом p(G) ориентированного графа называется отклоненность его центра.

В примере (рис. 3.29) r(G) = 2 (d(П) = d(Л) = 2). Если в графе нет центров, то полагают, что r(G) = ¥. В неориентированном графе r(G) – удаленность центра.

Диаметром неориентированного графа называется удален­ность периферийной вершины.