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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Похожие понятия[править | править вики-текст]

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

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

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

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

Центральной вершиной графа радиусом называется вершина, эксцентриситет которой равен . То есть вершина, на которой достигается радиус, или, что то же самое, вершина для которой .

Периферийной вершиной графа диаметра называется вершина, для которой расстояние равно до некоторой другой вершины. То есть вершина, на которой достигается диаметр. Формально, является периферийной, если .

Псевдопериферийной вершиной называется вершина, для которой любая вершина обладает свойством — если далека от насколько возможно, то далека от насколько возможно. Формально, вершина u является псевдопериферийной, если для любой вершины v с выполняется .

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

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

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

  1. Выберем вершину .
  2. Среди всех вершин, наиболее удалённых от , пусть имеет минимальную степень.
  3. Если , то возьмём и перейдём к шагу 2, в противном случае является псевдопериферийной вершиной.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Jérémie Bouttier, P. Di Francesco, E. Guitter Geodesic distance in planar graphs. — 2003. — Т. 663, вып. 3. — С. 535—567. — DOI:10.1016/S0550-3213(03)00355-9.
  2. Weisstein, Eric W. Graph Geodesic. MathWorld--A Wolfram Web Resource. Wolfram Research. — «The length of the graph geodesic between these points d(u,v) is called the graph distance between u and v»  Проверено 23 апреля 2008.
  3. F. Harary. Graph Theory. — МА: Addison-Wesley, 1969. — P. 199.