4446
правок
Протяженность геометрических сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Протяженность геометрических сетей (посмотреть исходный код)
Версия от 10:14, 20 февраля 2018
, 20 февраля 2018→Постановка задачи
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 10: | Строка 10: | ||
(1) <math>\sigma (p,q) := \frac{| \xi_G (p,q) |}{|pq|}</math> | (1) <math>\sigma (p,q) := \frac{| \xi_G (p,q) |}{|pq|}</math> | ||
представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. Протяженность сети G задается следующим образом: | представляет собой обход, по которому необходимо идти при перемещении по сети G из точки p в точку q, вместо того чтобы пройти напрямую. Здесь |.| обозначает евклидову длину. | ||
''Протяженность'' сети G задается следующим образом: | |||
(2) <math>\sigma(G) := max_{p \ne q \in V} \; \sigma(p, q)</math> | (2) <math>\sigma(G) := max_{p \ne q \in V} \; \sigma(p, q)</math> | ||
| Строка 18: | Строка 21: | ||
Пусть дано конечное множество S точек на плоскости. Требуется найти плоскую геометрическую сеть G = (V, E) | Пусть дано конечное множество S точек на плоскости. Требуется найти плоскую геометрическую сеть G = (V, E) с насколько возможно малой протяженностью <math>\sigma(G) \;</math>, такую, что S содержится в V. Значение | ||
<math>\Sigma(S) := inf \{ \sigma(G); G = (V, E) \;</math> – конечная плоская геометрическая сеть, | <math>\Sigma(S) := inf \{ \sigma(G); G = (V, E) \;</math> – конечная плоская геометрическая сеть, где <math>S \subset V \} \;</math> | ||
называется протяженностью множества точек S. Задача заключается в вычислении или ограничении <math>\Sigma(S) \;</math> для данного множества S. | называется ''протяженностью множества точек'' S. Задача заключается в вычислении или ограничении <math>\Sigma(S) \;</math> для данного множества S. | ||
== Родственные работы == | == Родственные работы == | ||