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

Перейти к навигации Перейти к поиску
Строка 129: Строка 129:




Случай 2. ex g Px \ Py и ey 2 Px \ Py. Очевидно, что length(ex) > length(ey). Тогда можно выбрать e0 = ex таким образом, что (Px [ Py) \ Q = Py. Следовательно, можно выбрать e00 = ey. Таким образом, выполняется равенство для (2).
Случай 2. <math>e_x \notin P_x \cap P_y</math> и <math>e_y \in 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).




Случай 3. ex 2 Px \ Py и ey 2 Px \ Py. Аналогично случаю 2.
Случай 3. <math>e_x \in P_x \cap P_y</math> и <math>e_y \notin P_x \cap P_y</math>. Аналогично случаю 2.




Случай 4. ex 2 Px \ Py и е;бР,ПРг. В этом случае length(ex) = length(ey) = length(e0). Таким образом, (2) верно. □
Случай 4. <math>e_x \in P_x \cap P_y</math> и <math>e_y \in P_x \cap P_y</math>. В этом случае <math>length(e_x) = length(e_y) = length(e') \;</math>. Таким образом, (2) верно. □




Далее поясняется, что субмодулярность gain(-) имеет место для k-ограниченного дерева Штейнера.
Далее поясняется, что субмодулярность gain(<math>\cdot</math>) имеет место для k-ограниченного дерева Штейнера.




Предположение. Пусть E – множество всех полных компонентов дерева Штейнера. Тогда gain(-) как функция от множества всех подмножеств E является субмодулярной.
'''Предположение'''. Пусть E – множество всех полных компонентов дерева Штейнера. Тогда gain(<math>\cdot</math>) как функция от множества всех подмножеств E является субмодулярной.


Доказательство. Заметим, что для любых H С E и x, y 2 E – H верно AxAymst(H) = 0,
Доказательство. Заметим, что для любых H С E и x, y 2 E – H верно AxAymst(H) = 0,
Источник — http://pco.iis.nsk.su/wega/index.php/Деревья_Штейнера