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

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

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

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

Основные определения[править | править вики-текст]

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

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

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

.

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

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

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

.

Периферийной вершиной графа диаметра называется вершина, эксцентриситет которой равен

.

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

Разбиение вершин графа на подмножества по их расстоянию от заданной начальной вершины называется структурой уровней[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.