4551
правка
Прямолинейное остовное дерево: различия между версиями
Материал из WEGA
Прямолинейное остовное дерево (посмотреть исходный код)
Версия от 12:09, 27 апреля 2016
, 27 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
'''Определение 2'''. Пусть имеется точка s; область R обладает свойством единственности относительно s, если для каждой пары точек <math>p, q \in R \;</math>, ||pq|| < max(||sp||, ||sq||). Разбиение пространства на конечном | '''Определение 2'''. Пусть имеется точка s; область R обладает свойством единственности относительно s, если для каждой пары точек <math>p, q \in R \;</math>, ||pq|| < max(||sp||, ||sq||). Разбиение пространства на конечном множестве непересекающихся областей обладает свойством единственности относительно s, если каждая из этих областей обладает свойством единственности относительно s. | ||
| Строка 42: | Строка 42: | ||
Предположим, что имеются точки p и q в <math>R_1 \;</math>. Без потери общности будем считать, что | Предположим, что имеются точки p и q в <math>R_1 \;</math>. Без потери общности будем считать, что <math>x_p \le x_q \;</math>. Если <math>y_p \le y_q \;</math>, то ||sq|| = ||sp|| + ||pq|| > ||pq||. Следовательно, необходимо рассмотреть только случай <math>y_p \ge y_q \;</math>. В этом случае <math>||pq|| = |x_p - x_q| + |y_p - y_q| = x_q - x_p + y_p - y_q = (x_q - y_q) + y_p - x_p < (x_s - y_s) + y_p - x_s = y_p - y_s \le x_p - x_s + y_p - y_s = ||sp||</math>. | ||
□ | □ | ||
