Расстояние (теория графов)

Длина кратчайшего пути между двумя узлами графа

В математической области теории графов расстояние между двумя вершинами в графе — это число ребер в кратчайшем пути (также называемом геодезическим графом ), соединяющем их. Это также известно как геодезическое расстояние или расстояние кратчайшего пути . ^[1] Обратите внимание, что между двумя вершинами может быть более одного кратчайшего пути. ^[2] Если нет пути, соединяющего две вершины, т. е. если они принадлежат разным связным компонентам , то условно расстояние определяется как бесконечное.

В случае ориентированного графа расстояние d ( u , v ) между двумя вершинами u и v определяется как длина кратчайшего ориентированного пути от u до v , состоящего из дуг, при условии, что существует хотя бы один такой путь. ^[3] Обратите внимание, что, в отличие от случая неориентированных графов, d ( u , v ) не обязательно совпадает с d ( v , u ) — так что это просто квазиметрика , и может быть так, что одна определена, а другая — нет.

Связанные концепции

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

Эксцентриситет ϵ ( v ) вершины v — это наибольшее расстояние между v и любой другой вершиной ; в символах:

${\displaystyle \epsilon (v)=\max _{u\in V}d(v,u).}$

Его можно рассматривать как расстояние, на котором узел находится от наиболее удаленного от него узла в графе.

Радиус r графа — это минимальный эксцентриситет любой вершины или, в символах ,

${\displaystyle r=\min _{v\in V}\epsilon (v)=\min _{v\in V}\max _{u\in V}d(v,u).}$

Диаметр d графа — это максимальный эксцентриситет любой вершины в графе. То есть, d — это наибольшее расстояние между любой парой вершин или, альтернативно,

${\displaystyle d=\max _{v\in V}\epsilon (v)=\max _{v\in V}\max _{u\in V}d(v,u).}$

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

Центральной вершиной в графе радиуса r называется вершина, эксцентриситет которой равен r , то есть вершина, расстояние от которой до самой дальней вершины равно радиусу, или, что то же самое, вершина v , такая, что ϵ ( v ) = r .

Периферийная вершина в графе диаметра d — это вершина, эксцентриситет которой равен d , то есть вершина, расстояние от которой до самой дальней вершины равно диаметру. Формально, v является периферийной, если ϵ ( v ) = d .

Псевдопериферийная вершина v обладает тем свойством, что для любой вершины u , если u находится как можно дальше от v , то v находится как можно дальше от u . Формально вершина v является псевдопериферийной, если для каждой вершины u с d ( u , v ) = ϵ ( v ) выполняется ϵ ( u ) = ϵ ( v ) .

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

Геодезический граф — это граф, в котором каждая пара вершин имеет уникальный кратчайший путь, соединяющий их. Например, все деревья являются геодезическими. ^[4]

Взвешенное расстояние кратчайшего пути обобщает геодезическое расстояние до взвешенных графов . В этом случае предполагается, что вес ребра представляет его длину или, для сложных сетей, стоимость взаимодействия, а взвешенное расстояние кратчайшего пути d ^W ( u , v ) является минимальной суммой весов по всем путям, соединяющим u и v . См. задачу о кратчайшем пути для получения более подробной информации и алгоритмов.

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

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

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

Смотрите также

• Матрица расстояний
• Расстояние сопротивления
• Центральность промежуточности
• Центральность
• Близость
• Проблема диаметра степени для графов и орграфов
• Метрический график

Примечания

1. Bouttier, Jérémie; Di Francesco, P.; Guitter, E. (июль 2003 г.). "Геодезическое расстояние в планарных графах". Nuclear Physics B . 663 (3): 535–567. arXiv : cond-mat/0303272 . Bibcode :2003NuPhB.663..535B. doi :10.1016/S0550-3213(03)00355-9. S2CID  119594729. Под расстоянием мы здесь подразумеваем геодезическое расстояние вдоль графа, а именно длину любого кратчайшего пути между, скажем, двумя заданными гранями
2. Weisstein, Eric W. "Graph Geodesic". MathWorld--A Wolfram Web Resource . Wolfram Research. Архивировано из оригинала 2008-04-23 . Получено 2008-04-23 . Длина геодезической линии графа между этими точками d(u,v) называется расстоянием графа между u и v.
3. Ф. Харари, Теория графов, Эддисон-Уэсли, 1969, стр.199.
4. Ойстейн Оре , Теория графов [3-е изд., 1967], Colloquium Publications, Американское математическое общество, стр. 104