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

Случай 1. ex g Px \ Py и ey 26 Px \ Py. Без потери общности будем считать, что length(ex) > length(ey). Тогда можно выбрать e0 = ex таким образом, что (Px [ Py) \ Q = Py. Следовательно, можно выбрать e00 = ey. Таким образом, выполняется равенство для (2).

Пусть F – множество трехлучевых звезд и ребер, выбранных жадным алгоритмом для вычисления итеративного 1-дерева Штейнера. Тогда gain(-) может и не быть субмодулярной на F . Чтобы убедиться в этом, рассмотрим две трехлучевых звезды x и y на рис. 2. Заметим, что gain(x [ y) > gain(x);gain(y) < 0 и gain(;) = 0. Наблюдается

gain(x [ y) — gain(x) — gain(y) + gain(;) > 0 :

== Применение ==