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

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

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

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

Псевдо-периферийная вершина обладает свойством , что для любой вершины , если это так далеко от , насколько это возможно, то есть , как далеко от , насколько это возможно. Формально вершина U является псевдо-периферийным, если для каждой вершины V с имеет место .${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$${\displaystyle v}$${\displaystyle d(u,v)=\epsilon (u)}$${\displaystyle \epsilon (u)=\epsilon (v)}$

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

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

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

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

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

См. Также [ править ]

Заметки [ править ]