4551
правка
Деревья Штейнера: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 141: | Строка 141: | ||
'''Предположение'''. Пусть E – множество всех полных компонентов дерева Штейнера. Тогда gain(<math>\cdot</math>) как функция от множества всех подмножеств E является субмодулярной. | '''Предположение'''. Пусть <math>\mathcal{E} \;</math> – множество всех полных компонентов дерева Штейнера. Тогда gain(<math>\cdot</math>) как функция от множества всех подмножеств <math>\mathcal{E} \;</math> является субмодулярной. | ||
Доказательство. Заметим, что для любых H | Доказательство. Заметим, что для любых <math>\mathcal{H} \subset \mathcal{E} \;</math> и <math>x, y \in \mathcal{E} - \mathcal{H} \;</math> верно <math>\Delta_x \Delta_y mst(H) = 0 \;</math>, где <math>H = \cup_{z \in \mathcal{H}} z \;</math>. Таким образом, верность предположения следует из леммы 2. □ | ||
где H = | |||
Пусть F – множество трехлучевых звезд и ребер, выбранных жадным алгоритмом для вычисления итеративного 1-дерева Штейнера. Тогда gain( | Пусть <math>\mathcal{F} \;</math> – множество трехлучевых звезд и ребер, выбранных жадным алгоритмом для вычисления итеративного 1-дерева Штейнера. Тогда gain(<math>\cdot</math>) может и не быть субмодулярной на <math>\mathcal{F} \;</math>. Чтобы убедиться в этом, рассмотрим две трехлучевых звезды x и y на рис. 2. Заметим, что <math>gain(x \cup y) > gain(x), gain(y) \le 0, gain(\empty) = 0 \;</math>. Имеет место соотношение | ||
gain(x | <math>gain(x \cup y) - gain(x) - gain(y) + gain(\empty) > 0 \;</math>. | ||