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

Пусть 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). Множество всех центральных вершин графа называется его центром.