PROFILPELAJAR.COM

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

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

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

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

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

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