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

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

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

Связанные понятия

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

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

[1] Бутье, Жереми; Ди Франческо, П.; Гиттер, Э. (июль 2003 г.). «Геодезическое расстояние в плоских графах». Ядерная физика Б . 663 (3): 535–567. arXiv : cond-mat/0303272 . Бибкод : 2003НуФБ.663..535Б . дои : 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

[1]

[2]

[3]

[4]