Русская Википедия:Метрика кратчайшего пути
Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между даннымми вершинами. Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным.
В случае ориентированных графов расстояние <math>d(u,v)</math> между двумя вершинами <math>u</math> и <math>v</math> определяется как длина кратчайшего пути из <math>u</math> в <math>v</math>, состоящий из дуг[1]. В отличие от случая неориентированных графов <math>d(u,v)</math> может не совпадать с <math>d(v,u)</math> и даже может случиться, что одно расстояние существует, а другое — нет.
Основные определения
Метрическое пространство, определённое на множестве точек в терминах расстояния в графе, называется метрикой графа. Множество вершин (неориентированного графа) и функция расстояния образуют метрическое пространство в том и только в том случае, когда граф связен.
Эксцентриситетом <math>\epsilon(v)</math> вершины <math>v</math> называется наибольшее геодезическое расстояние между <math>v</math> и любой другой вершиной графа. То есть расстояние до самой дальней от <math>v</math> вершины графа.
- <math>\epsilon(v) = \max_{u \in V}d(v,u)</math>
Радиусом <math>r</math> графа называется минимальный эксцентриситет среди всех вершин графа
- <math>r = \min_{v \in V} \epsilon(v)</math>.
Диаметром <math>d</math> графа называется максимальный эксцентриситет среди всех вершин графа. Таким образом, <math>d</math> — это наибольшее расстояние между всеми парами вершин графа
- <math>d = \max_{v \in V}\epsilon(v)</math>
Чтобы найти диаметр графа сначала находят кратчайшие пути между всеми парами вершин. Наибольшая длина кратчайшего пути есть диаметр графа.
Центральной вершиной графа радиусом <math>r</math> называется вершина, эксцентриситет которой равен <math>r</math>. То есть вершина, на которой достигается радиус
- <math>\epsilon(v) = r</math>.
Периферийной вершиной графа диаметра <math>d</math> называется вершина, эксцентриситет которой равен <math>d</math>
- <math>\epsilon(v) = d</math>.
Псевдопериферийной вершиной <math>v</math> называется вершина, для которой любая вершина <math>u</math> обладает свойством — если <math>v</math> далека от <math>u</math> насколько возможно, то <math>u</math> далека от <math>v</math> насколько возможно. Формально, вершина <math>u</math> является псевдопериферийной, если для любой вершины <math>v</math> с <math>d(u,v) = \epsilon(u)</math> выполняется <math>\epsilon(u)=\epsilon(v)</math>.
Разбиение вершин графа на подмножества по их расстоянию от заданной начальной вершины называется Шаблон:Не переведено 5 графа.
Алгоритм поиска псевдопериферийных вершин
Часто алгоритмам для разреженных матриц необходима начальная вершина с высоким эксцентриситетом. Лучше бы использовать периферийную вершину, но в большом графе её трудно найти. В большинстве случаев можно использовать псевдопериферийные вершины. Псевдопериферийную вершину можно легко найти, используя следующий алгоритм:
- Выберем вершину <math>u</math>.
- Среди всех вершин, наиболее удалённых от <math>u</math>, пусть <math>v</math> имеет минимальную степень.
- Если <math>\epsilon(v) > \epsilon(u)</math>, то возьмём <math>u=v</math> и перейдём к шагу 2, в противном случае <math>v</math> является псевдопериферийной вершиной.
См. также
- Матрица расстояний
- Резистивное расстояние
- Промежуточность
- Центральность
- Близость
- Проблема размера — диаметра графов и ориентированных графов
Примечания
Литература
