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

В случае ориентированных графов расстояние ${\displaystyle d(u,v)}$ между двумя вершинами ${\displaystyle u}$ и ${\displaystyle v}$ определяется как длина кратчайшего пути из ${\displaystyle u}$ в ${\displaystyle v}$ , состоящий из дуг . В отличие от случая неориентированных графов ${\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)}$ .

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

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

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

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 .