Расстояние в графах. Центральные и периферийные вершины

Пусть G=<M,R> - связный неорграф, a,b – две его несовпадающие вершины. Длина кратчайшего (a,b) -маршрута называется расстоянием между вершинами a и b и обозначается ρ(a,b). Положим ρ(a,a)=0.

Аксиомы метрики:

1) ρ(a,b) ≥0;

2) ρ(a,b) =0 ó a=b

3) ρ(a,b)= ρ(b,a) (симметричность)

4) ρ(a,b)≤ ρ(a,с)+ ρ(с,b) (неравенство треугольника)

Если M={a₁,…,a_n}, то матрица P=(p_ij), в которой p_ij=ρ(a_i,a_j), называется матрицей расстояний. Заметим, что P^T=P.

Эксцентриситетом вершины a называется величина .

Максимальный среди всех эксцентриситетов вершин называется диаметром графа G и обозначается через d(G): . Вершина a называется периферийной, если e(a)=d(G). Минимальный из эксцентриситетов графа G называется его радиусом r(G): . Вершина a называется центральной, если e(a)=r(G). Множество всех центральных вершин графа называется его центром.