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

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

В математической области теории графов расстояние между двумя вершинами графа — это количество ребер на кратчайшем пути (также называемом геодезической графа ) , соединяющем их. Это также известно как геодезическое расстояние или расстояние кратчайшего пути . ^[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 ) представляет собой минимальную сумму весов по всем путям . соединяя тебя и v . Более подробную информацию и алгоритмы см. в задаче о кратчайшем пути .

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

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

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

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

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

Примечания

1. Бутье, Жереми; Ди Франческо, П.; Гиттер, Э. (июль 2003 г.). «Геодезическое расстояние в плоских графах». Ядерная физика Б . 663 (3): 535–567. arXiv : cond-mat/0303272 . Бибкод : 2003NuPhB.663..535B. дои : 10.1016/S0550-3213(03)00355-9. S2CID  119594729. Под расстоянием здесь мы подразумеваем геодезическое расстояние вдоль графа, а именно длину любого кратчайшего пути между, скажем, двумя заданными гранями.
2. Вайсштейн, Эрик В. «Граф геодезический». MathWorld — веб-ресурс Wolfram . Вольфрам Исследования. Архивировано из оригинала 23 апреля 2008 г. Проверено 23 апреля 2008 г. Длина графической геодезической между этими точками d(u,v) называется графическим расстоянием между u и v.
3. Ф. Харари, Теория графов, Аддисон-Уэсли, 1969, стр.199.
4. Ойстейн Оре , Теория графов [3-е изд., 1967], Публикации коллоквиума, Американское математическое общество, стр. 104