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