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

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

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

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

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

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

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

Радиусом r графа называется минимальный эксцентриситет любой вершины, или, формально, r = \min_{v \in V} \epsilon(v).

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

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

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

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

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

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

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

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

Смотрите также[править | править исходный текст]

Примечания[править | править исходный текст]

  1. Jérémie Bouttier, Di Francesco, P. ,Guitter, E. Geodesic distance in planar graphs. — 2003. — В. 3. — Т. 663. — С. 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.