Рассмотрим взвешенный граф G=(V,E,w). Нам дано семейство подмножеств вершин V_i.
Лес Штейнера — это лес, который для каждого подмножества вершин V_i соединяет все вершины в этом подмножестве с деревом.
Пример: только одно подмножество V_1 = V. В этом случае лес Штейнера является остовным деревом всего графа.
Пример: граф P4 (путь с 4 вершинами) и два подмножества: V_1 = {v1, v4} и V_2 = {v2, v3}. Дерево Штейнера для этого примера — это весь граф.
Достаточно теории. Найти такой лес с минимальным весом сложно (NP-полно). Знаете ли вы более быстрый приближенный алгоритм для поиска такого леса с неоптимальным весом?
