Метрика кратчайшего пути
Метрика кратчайшего пути — метрика на вершинах графа равная числу рёбер в кратчайшем пути между данными вершинами. Если нет пути между двумя вершинами, то есть если они принадлежат различным компонентам связности, то принято считать расстояние бесконечным.
В случае ориентированных графов расстояние между двумя вершинами и определяется как длина кратчайшего пути из в , состоящий из дуг[1]. В отличие от случая неориентированных графов может не совпадать с и даже может случиться, что одно расстояние существует, а другое — нет.
Основные определения
[править | править код]Метрическое пространство, определённое на множестве точек в терминах расстояния в графе, называется метрикой графа. Множество вершин (неориентированного графа) и функция расстояния образуют метрическое пространство в том и только в том случае, когда граф связен.
Эксцентриситетом вершины называется наибольшее геодезическое расстояние между и любой другой вершиной графа. То есть расстояние до самой дальней от вершины графа.
Радиусом графа называется минимальный эксцентриситет среди всех вершин графа
- .
Диаметром графа называется максимальный эксцентриситет среди всех вершин графа. Таким образом, — это наибольшее расстояние между всеми парами вершин графа
Чтобы найти диаметр графа сначала находят кратчайшие пути между всеми парами вершин. Наибольшая длина кратчайшего пути есть диаметр графа.
Центральной вершиной графа радиусом называется вершина, эксцентриситет которой равен . То есть вершина, на которой достигается радиус
- .
Периферийной вершиной графа диаметра называется вершина, эксцентриситет которой равен
- .
Псевдопериферийной вершиной называется вершина, для которой любая вершина обладает свойством — если далека от насколько возможно, то далека от насколько возможно. Формально, вершина является псевдопериферийной, если для любой вершины с выполняется .
Разбиение вершин графа на подмножества по их расстоянию от заданной начальной вершины называется структурой уровней[англ.] графа.
Алгоритм поиска псевдопериферийных вершин
[править | править код]Часто алгоритмам для разреженных матриц необходима начальная вершина с высоким эксцентриситетом. Лучше бы использовать периферийную вершину, но в большом графе её трудно найти. В большинстве случаев можно использовать псевдопериферийные вершины. Псевдопериферийную вершину можно легко найти, используя следующий алгоритм:
- Выберем вершину .
- Среди всех вершин, наиболее удалённых от , пусть имеет минимальную степень.
- Если , то возьмём и перейдём к шагу 2, в противном случае является псевдопериферийной вершиной.
См. также
[править | править код]- Матрица расстояний
- Резистивное расстояние
- Промежуточность
- Центральность
- Близость
- Проблема размера — диаметра графов и ориентированных графов
Примечания
[править | править код]- ↑ F. Harary. Graph Theory. — МА: Addison-Wesley, 1969. — P. 199.
Литература
[править | править код]- Деза М., Лоран M. Геометрия разрезов и метрик. — Москва: МЦНМО, 2001. — ISBN 5-900916-84-7.