Расстояние в графах

Пусть G = (V, X) – связный неориентированный граф.

v ₁, v ₂ – две его несовпадающие вершины.

Определение: Расстоянием между вершинами v _i и v _j называется длина кратчайшего (v _i , v _j) – маршрута. Обозначается ρ (v _i , v _j).

Введенное таким образом расстояние удовлетворяет следующим аксиомам метрики:

1) ρ (v _i , v _j) ≥ 0;

2) ρ (v _i , v _j) = 0 <=> v _i = v _j (если i = j);

3) ρ (v _i , v _j) = ρ (v _i , v _j) – симметричность;

4) ρ (v _i , v _j) ≤ ρ (v _i ,w) + ρ (w , v _j) – неравенство треугольника;

5) ρ (v _i , v _j) < ∞

Определение: Пусть G = (V, X). Если V = { v ₁, v ₂, …, v _n}, то матрицейрасстояний называется матрица P = [ p _ij] порядка n, у которой:

p _ij = ρ(v _i,v _j) (i = 1,…, n; j = 1,…, n)

Замечание: P^T = P, т. е. матрица P симметрична.

Определение: Для фиксированной вершины v величина

е(v) = max {ρ(v,w) | w V} называется эксцентриситетом вершины v. Таким образом, эксцентриситет вершины равен расстоянию от данной вершины до наиболее удаленной от нее.

Если P – матрица расстояний, то эксцентриситет е(v _i) равен наибольшему из чисел, стоящих в i-й строке.

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

Обозначается d(G). d(G) = max {е(v _i) / v _i V }.

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

Определение: Минимальный из эксцентриситетов графа G называется его радиусом. Обозначается r(G), т. е. r(G) = min {е(v _i) | v _i V }.

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