4501
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 129: | Строка 129: | ||
Случай 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. | Случай 3. <math>e_x \in P_x \cap P_y</math> и <math>e_y \notin P_x \cap P_y</math>. Аналогично случаю 2. | ||
Случай 4. | Случай 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( | Далее поясняется, что субмодулярность gain(<math>\cdot</math>) имеет место для k-ограниченного дерева Штейнера. | ||
Предположение. Пусть E – множество всех полных компонентов дерева Штейнера. Тогда gain( | '''Предположение'''. Пусть 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, | ||