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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \epsilon (v)=r}$.

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

${\displaystyle \epsilon (v)=d}$.

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

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

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

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

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

См. также

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

Примечания

Литература

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

Эта страница в последний раз была отредактирована 11 ноября 2022 в 11:10.