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

'''Теорема 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.'''