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

В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 1 на меньшие деревья, в которых каждый полюс является листом. В такой декомпозиции каждое полученное маленькое дерево называется [[полный компонент|полным компонентом]]. Размер полного компонента равен количеству содержащихся в нем полюсов. Дерево Штейнера является k-ограниченным, если каждый его полный компонент имеет размер не более k. Кратчайшее k-ограниченное дерево Штейнера также называется k-ограниченным [[минимальное дерево Штейнера|минимальным деревом Штейнера]]. Обозначим его длину за <math>smt_k(P) \;</math>. Очевидно, что <math>smt_2(P) \;</math> – длина минимального остовного дерева на P, также обозначаемая как mst(P). Пусть smt(P) обозначает длину минимального дерева Штейнера на P. Если значение <math>smt_3(P) \;</math> можно вычислить за полиномиальное время, то этот способ лучше подходит для аппроксимации smt(P) по сравнению с mst(P). Однако до сих пор для <math>smt_3(P) \;</math> не было найдено аппроксимации с полиномиальным временем. Поэтому Зеликовский [14] использовал жадную аппроксимацию <math>smt_3(P) \;</math> для аппроксимации smt(P). Чанг [4, 5] использовал похожий жадный алгоритм для вычисления итеративного 1-дерева Штейнера. Пусть <math>\mathcal{F} \;</math> – семейство подграфов исходного графа G с взвешенными ребрами. Для любого связного подграфа H обозначим за mst(H) длину минимального остовного дерева H, а за mst(H) – сумму mst(H') для H' по всем связным компонентам H для любого подграфа H.