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

Задачу построения леса Штейнера можно определить альтернативным образом при помощи не пар, а групп полюсов <math>R = \{ g_1, ..., g_k \} \;</math>, где <math>g_i \subseteq V \;</math>. Задача заключается в вычислении подграфа с минимальной стоимостью, такого, что все полюса, принадлежащие к одной и той же группе, связаны друг с другом. Определение эквивалентно предыдущему.

== Родственные задачи ==

Очевидно, что в случае, когда <math>r(x, y) \in \{ 0, 1 \} \;</math> для всех <math>(x, y) \in V \times V \;</math>, эта задача сводится к задаче построения леса Штейнера.

== Основные результаты ==

'''Теорема 1. Существует алгоритм аппроксимации, который для каждого экземпляра I = (G, c, R) задачи построения леса Штейнера вычисляет допустимый лес F, такой, что <math>c(F) \le \Big( 2 - \frac{1}{k} \Big) \cdot OPT(I) \;</math>, где k – количество пар полюсов в R, а OPT(I) – стоимость оптимального леса Штейнера для I.'''

== Родственные работы ==