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

Перейти к навигации Перейти к поиску
Строка 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).




Источник — http://pco.iis.nsk.su/wega/index.php/Деревья_Штейнера