double arrow

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


Пусть 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={a1,…,an}, то матрица P=(pij), в которой pij=ρ(ai,aj), называется матрицей расстояний. Заметим, что PT=P.

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

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


Сейчас читают про: