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

Пусть 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).

Определение: Множество всех центральных вершин графа называeтся его центром.

Пример:

Составим матрицу расстояний P =

e(1) = 2, e(2) = 1, e(3) = 2. e(4) = 2, e(5) = 2, тогда

d(G) = 2. Периферийные вершины: 1, 3, 4, 5.

r(G) = 1, центр {2}. (центр может состоять из нескольких вершин).

Теорема: В полном графе K_n d(K_n) = r(K_n) = 1 (т. к. все различные вершины графа K_n смежны).

Задача нахождения центральных вершин возникает в практической деятельности людей.

Например, граф представляет собой сеть дорог, т. е. вершины соответствуют населенным пунктам, а ребра – дорогам между ними. Требуется оптимально разместить больницы, пункты обслуживания и т. п. В подобных ситуациях оптимизация заключается в минимизации расстояния от места обслуживания до наиболее удаленного населенного пункта. Следовательно, местами размещения должны быть центральные вершины графа. Реальные задачи отличаются от этой идеальной тем, что приходится учитывать и другие обстоятельства – расстояния между населенными пунктами, стоимость, время проезда и т. д. Для учета этих параметров используются взвешенные графы (нагруженные).