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

редактировать

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

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

Содержание

  • 1 Понятия, связанные с данным
  • 2 Алгоритм для поиска псевдопериферийных вершин
  • 3 См. Также
  • 4 Примечания

Понятия, связанные с данным

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

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

radiusr {\ displaystyle r}r графа - это минимальный эксцентриситет любой вершины или, выражаясь символами, r = min v ∈ В ϵ (v) знак равно min v ∈ V max u ∈ V d (v, u) {\ displaystyle r = \ min _ {v \ in V} \ epsilon (v) = \ min _ {v \ in V } \ max _ {u \ in V} d (v, u)}{\ displaystyle r = \ min _ {v \ in V} \ epsilon (v) = \ min _ {v \ in V} \ max _ {u \ in V} d (v, u)} .

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

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

A периферийная вершина на графике диаметром d {\ displaystyle d}d - это вершина, которая находится на расстоянии d {\ displaystyle d}d от некоторая другая вершина, то есть вершина, которая достигает диаметра. Формально v {\ displaystyle v}v является периферийным, если ϵ (v) = d {\ displaystyle \ epsilon (v) = d}\ epsilon (v) = d .

A псевдопериферийная вершина v {\ displaystyle v}v имеет свойство, которое для любой вершины u {\ displaystyle u}u , если v {\ displaystyle v}v находится как можно дальше от u {\ displaystyle u}u , тогда u {\ displaystyle u}u так же далеко от v {\ displaystyle v}v насколько возможно. Формально вершина u является псевдопериферийной, если для каждой вершины v с d (u, v) = ϵ (u) {\ displaystyle d (u, v) = \ epsilon (u)}d (u, v) = \ epsilon (u) содержит ϵ (u) = ϵ (v) {\ displaystyle \ epsilon (u) = \ epsilon (v)}\ epsilon (u) = \ epsilon (v) .

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

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

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

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

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

См. также

Примечания

Последняя правка сделана 2021-05-17 09:10:57
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте