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

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

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

Эксцентриситетом ${\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}$ является псевдопериферийной вершиной.