Прямолинейное остовное дерево: различия между версиями

Предположим, что имеются точки 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>.