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

Рассмотрим входной граф с взвешенными ребрами G = (V, E) для задачи построения NST (сетевого дерева Штейнера). Предположим, что G – полный граф и что веса ребер удовлетворяют неравенству треугольника. В противном случае рассмотрим полный граф на V, в котором каждое ребро (u, v) имеет вес, равный длине кратчайшего пути между u и v в графе G. Пусть дано множество полюсов P; деревом Штейнера является дерево, связывающее все указанные полюса таким образом, что каждый лист является полюсом.

В дереве Штейнера полюс может иметь степень больше единицы. Можно провести декомпозицию дерева Штейнера, разбив все вершины со степенью больше 1 на меньшие деревья, в которых каждый полюс является листом. В такой декомпозиции каждое полученное маленькое дерево называется полным компонентом. Размер полного компонента равен количеству содержащихся в нем полюсов. Дерево Штейнера является k-ограниченным, если каждый его полный компонент имеет размер не более k. Кратчайшее k-ограниченное дерево Штейнера также называется k-ограниченным минимальным деревом Штейнера. Обозначим его длину за smtk(P). Очевидно, что smt2(P) – длина минимального остовного дерева на P, также обозначаемая как mst(P). Пусть smt(P) обозначает длину минимального дерева Штейнера на P. Если значение smt3(P) можно вычислить за полиномиальное время, то этот способ лучше подходит для аппроксимации smt(P) по сравнению с mst(P). Однако до сих пор для smt3(P) не было найдено аппроксимации с полиномиальным временем. Поэтому Зеликовский [14] использовал жадную аппроксимацию smt3 (P) для аппроксимации smt(P). Чанг [4 , 5] использовал похожий жадный алгоритм для вычисления итеративного 1-дерева Штейнера. Пусть F – семейство подграфов исходного графа G с взвешенными ребрами. Для любого связного подграфа H обозначим за mst(H) длину минимального остовного дерева H, а за mst(H) – сумму mst(H0) для H0 по всем связным компонентам H для любого подграфа H.