Метрика кратчайшего пути

Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между данными вершинами. Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным.

В случае ориентированных графов расстояние $d(u,v)$ между двумя вершинами $u$ и $v$ определяется как длина кратчайшего пути из $u$ в $v$, состоящего из дуг. В отличие от случая неориентированных графов $d(u,v)$ может не совпадать с $d(v,u)$ и даже может случиться, что одно расстояние существует, а другое — нет.

Основные определения

Метрическое пространство, определённое на множестве точек в терминах расстояния в графе, называется метрикой графа. Множество вершин (неориентированного графа) и функция расстояния образуют метрическое пространство в том и только в том случае, когда граф связен.

Эксцентриситетом $\epsilon (v)$ вершины $v$ называется наибольшее геодезическое расстояние между $v$ и любой другой вершиной графа. То есть расстояние до самой дальней от $v$ вершины графа.

$\epsilon (v)=\max _{u\in V}d(v,u)$

Радиусом $r$ графа называется минимальный эксцентриситет среди всех вершин графа

$r=\min _{v\in V}\epsilon (v)$.

Диаметром $d$ графа называется максимальный эксцентриситет среди всех вершин графа. Таким образом, $d$ — это наибольшее расстояние между всеми парами вершин графа

$d=\max _{v\in V}\epsilon (v)$

Чтобы найти диаметр графа сначала находят кратчайшие пути между всеми парами вершин. Наибольшая длина кратчайшего пути есть диаметр графа.

Центральной вершиной графа радиусом $r$ называется вершина, эксцентриситет которой равен $r$. То есть вершина, на которой достигается радиус

$\epsilon (v)=r$.

Периферийной вершиной графа диаметра $d$ называется вершина, эксцентриситет которой равен $d$

$\epsilon (v)=d$.

Псевдопериферийной вершиной $v$ называется вершина, для которой любая вершина $u$ обладает свойством — если $v$ далека от $u$ насколько возможно, то $u$ далека от $v$ насколько возможно. Формально, вершина $u$ является псевдопериферийной, если для любой вершины $v$ с $d(u,v)=\epsilon (u)$ выполняется $\epsilon (u)=\epsilon (v)$.

Разбиение вершин графа на подмножества по их расстоянию от заданной начальной вершины называется структурой уровней графа.

Алгоритм поиска псевдопериферийных вершин

Часто алгоритмам для разреженных матриц необходима начальная вершина с высоким эксцентриситетом. Лучше бы использовать периферийную вершину, но в большом графе её трудно найти. В большинстве случаев можно использовать псевдопериферийные вершины. Псевдопериферийную вершину можно легко найти, используя следующий алгоритм:

1. Выберем вершину $u$.
2. Среди всех вершин, наиболее удалённых от $u$, пусть $v$ имеет минимальную степень.
3. Если $\epsilon (v)>\epsilon (u)$, то возьмём $u=v$ и перейдём к шагу 2, в противном случае $v$ является псевдопериферийной вершиной.

См. также

• Матрица расстояний
• Резистивное расстояние
• Промежуточность
• Центральность
• Близость
• Проблема размера — диаметра графов и ориентированных графов

Литература

• Деза М., Лоран M. Геометрия разрезов и метрик. — Москва: МЦНМО, 2001. — ISBN 5-900916-84-7.