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

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




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


Доказательство. Заметим, что для любых H С E и x, y 2 E – H верно AxAymst(H) = 0,
Доказательство. Заметим, что для любых <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 = [z2Hz. Таким образом, верность предположения следует из леммы 2. □




Пусть F – множество трехлучевых звезд и ребер, выбранных жадным алгоритмом для вычисления итеративного 1-дерева Штейнера. Тогда gain(-) может и не быть субмодулярной на F . Чтобы убедиться в этом, рассмотрим две трехлучевых звезды x и y на рис. 2. Заметим, что gain(x [ y) > gain(x);gain(y) < 0 и gain(;) = 0. Наблюдается
Пусть <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 [ y) — gain(x) — gain(y) + gain(;) > 0 :
<math>gain(x \cup y) - gain(x) - gain(y) + gain(\empty) > 0 \;</math>.




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