Расстояние (теория графов) - Distance (graph theory)

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

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

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

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

В эксцентриситет ${ displaystyle epsilon (v)}$ вершины ${ displaystyle v}$ это наибольшее расстояние между ${ displaystyle v}$ и любая другая вершина; в символах, что ${ displaystyle epsilon (v) = max _ {u in V} d (v, u)}$ . Можно представить себе, как далеко узел находится от наиболее удаленного от него узла на графике.

В радиус ${ displaystyle r}$ графа - это минимальный эксцентриситет любой вершины или, в символах, ${ displaystyle r = min _ {v in V} epsilon (v) = min _ {v in V} max _ {u in V} d (v, u)}$ .

В диаметр ${ displaystyle d}$ графа - это максимальный эксцентриситет любой вершины графа. Это, ${ displaystyle d}$ - наибольшее расстояние между любой парой вершин или, наоборот, ${ displaystyle d = max _ {v in V} epsilon (v)}$ . Чтобы найти диаметр графа, сначала найдите кратчайший путь между каждой парой вершины. Наибольшая длина любого из этих путей - это диаметр графа.

А центральная вершина в графике радиуса ${ displaystyle r}$ тот, чья эксцентричность ${ displaystyle r}$ - то есть вершина, которая достигает радиуса или, что то же самое, вершина ${ displaystyle v}$ такой, что ${ displaystyle epsilon (v) = r}$ .

А периферическая вершина в графике диаметра ${ displaystyle d}$ это то, что расстояние ${ displaystyle d}$ из некоторой другой вершины, то есть вершины, которая достигает диаметра. Формально, ${ displaystyle v}$ периферический, если ${ displaystyle epsilon (v) = d}$ .

А псевдопериферическая вершина ${ displaystyle v}$ обладает тем свойством, что для любой вершины ${ displaystyle u}$ , если ${ displaystyle v}$ так же далеко от ${ displaystyle u}$ насколько возможно, тогда ${ displaystyle u}$ так же далеко от ${ displaystyle v}$ насколько возможно. Формально вершина ты является псевдопериферическим, если для каждой вершины v с участием ${ Displaystyle д (и, v) = эпсилон (и)}$ держит ${ Displaystyle epsilon (u) = epsilon (v)}$ .

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

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

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

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

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

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

Заметки

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

[1] Буттье, Жереми; Di Francesco, P .; Гиттер, Э. (июль 2003 г.). «Геодезические расстояния в плоских графах». Ядерная физика B. 663 (3): 535–567. arXiv:cond-mat / 0303272. Дои:10.1016 / S0550-3213 (03) 00355-9. Под расстоянием мы понимаем здесь геодезическое расстояние вдоль графика, а именно длину любого кратчайшего пути между двумя заданными гранями.

[2] Вайсштейн, Эрик В. «Граф геодезический». MathWorld - веб-ресурс Wolfram. Wolfram Research. Получено 2008-04-23. Длина геодезической графа между этими точками d (u, v) называется расстоянием графа между u и v

[3] Ф. Харари, Теория графов, Эддисон-Уэсли, 1969, стр.199.

[4] Øystein Ore, Теория графов [3-е изд., 1967], Публикации коллоквиума, Американское математическое общество, с. 104

[1]

[2]

[3]

[4]