Деревья Штейнера: различия между версиями

Деревья Штейнера (посмотреть исходный код)

123 байта добавлено , 2 июня 2016

4501

правка

Версия от 12:39, 2 июня 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) ← Предыдущая правка		Версия от 13:13, 2 июня 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) (→‎Основные результаты) Следующая правка →
Строка 126:		Строка 126:


	Случай 1. ~~ex g Px~~ \ Py и ~~ey 26 Px~~ \ Py. Без потери общности будем считать, что length(ex) > length(ey). Тогда можно выбрать e0 = ex таким образом, что (~~Px [ Py~~) \ Q = Py. Следовательно, можно выбрать ~~e00~~ = ey. Таким образом, выполняется равенство для (2).		Случай 1. <math>e_x \notin P_x \cap P_y</math> и <math>e_y \notin P_x \cap P_y</math>. Без потери общности будем считать, что <math>length(e_x) \ge length(e_y) \;</math>. Тогда можно выбрать <math>e' = e_x \;</math> таким образом, что <math>(P_x \cup P_y) \cap Q = P_y</math>. Следовательно, можно выбрать <math>e'' = e_y \;</math>. Таким образом, выполняется равенство для (2).