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

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

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

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

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

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

[math]\displaystyle{ \epsilon(v) = \max_{u \in V}d(v,u) }[/math]

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

[math]\displaystyle{ r = \min_{v \in V} \epsilon(v) }[/math].

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

[math]\displaystyle{ d = \max_{v \in V}\epsilon(v) }[/math]

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

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

[math]\displaystyle{ \epsilon(v) = r }[/math].

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

[math]\displaystyle{ \epsilon(v) = d }[/math].

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

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

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

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

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

См. также

Примечания

↑ F. Harary. Graph Theory. — МА: Addison-Wesley, 1969. — P. 199.

Литература

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

[1] F. Harary. Graph Theory. — МА: Addison-Wesley, 1969. — P. 199.

[1]