4551
правка
Протяженность геометрических сетей: различия между версиями
Перейти к навигации
Перейти к поиску
Протяженность геометрических сетей (посмотреть исходный код)
Версия от 11:59, 13 февраля 2018
, 13 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 7: | Строка 7: | ||
Пусть G = (V, E) – плоская геометрическая сеть, множество вершин V которой является конечным множеством местоположений точек в пространстве <math>\mathbb{R}^2 \;</math>, связанных множеством ребер E, состоящим из непересекающихся прямолинейных отрезков с конечными точками в V. Обозначим для двух точек <math>p \ne q \in V \;</math> за <math>\xi_G (p,q) \;</math> [[кратчайший путь]] из p в q в сети G. Тогда | Пусть G = (V, E) – плоская геометрическая сеть, множество вершин V которой является конечным множеством местоположений точек в пространстве <math>\mathbb{R}^2 \;</math>, связанных множеством ребер E, состоящим из непересекающихся прямолинейных отрезков с конечными точками в V. Обозначим для двух точек <math>p \ne q \in V \;</math> за <math>\xi_G (p,q) \;</math> [[кратчайший путь]] из p в q в сети G. Тогда | ||
(1) | |||
(1) <math>\sigma (p,q) := \frac{| \xi_G (p,q) |}{|pq|}</math> | |||
представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. Протяженность сети G задается следующим образом: | представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. Протяженность сети G задается следующим образом: | ||
(2) | |||
(2) <math>\sigma(G) := max_{p \ne q \in V} \; \sigma(p, q)</math> | |||
Это значение также называется ''коэффициентом растяжения'' G. Его не следует смешивать с ''геометрической протяженностью'' сети, в которой помимо вершин учитываются также точки на ребрах. | |||
Пусть дано конечное множество S точек на плоскости. Требуется найти плоскую геометрическую сеть G = (V, E), протяженность которой <math>\sigma(G) \;</math> насколько возможно мала, такую, что S содержится в V. Значение | |||
<math>\Sigma(S) := inf \{ \sigma(G); G = (V, E) \;</math> – конечная плоская геометрическая сеть, в которой <math>S \subset V \} \;</math> | |||
называется протяженностью множества точек S. Задача заключается в вычислении или ограничении <math>\Sigma(S) \;</math> для данного множества S. | |||