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

Ребро <math>e \in E \;</math> является ''плотным'', если соответствующее ограничение (3) выполняется в виде равенства; путь является плотным, если все составляющие его ребра являются плотными. Пусть <math>H^{ \tau} \;</math> – подграф G, порожденный плотными ребрами для двойственного значения <math>y^{ \tau} \;</math>. Связные компоненты <math>H^{ \tau} \;</math> порождают разбиение <math>C^{ \tau} \;</math> на множестве вершин V. Пусть <math>\mathcal{S}^{ \tau} \;</math> – множество всех разрезов Штейнера, содержащихся в <math>C^{ \tau} \;</math>, т.е. <math>\mathcal{S}^{ \tau} = C^{ \tau} \cap \mathcal{S} \;</math>. Алгоритм AKR равномерно увеличивает двойственные значения <math>y_S \;</math> для всех множеств <math>S \in \mathcal{S}^{ \tau} \;</math> во все моменты времени <math>\tau \ge 0 \;</math>. Заметим, что <math>y^{ \tau} \;</math> является допустимым для двойственной задачи. Алгоритм поддерживает инвариант: <math>F^{ \tau} \;</math> в любой момент времени является подграфом <math>H^{ \tau} \;</math>. Рассмотрим событие, при котором путь P между двумя деревьями <math>T_1 \;</math> и <math>T_2 \;</math> в <math>F^{ \tau} \;</math> становится плотным. После этого недостающие ребра P добавляются к <math>F^{ \tau} \;</math> и процесс продолжается. В конечном итоге все деревья <math>F^{ \tau} \;</math> становятся неактивными, в результате чего процесс завершается.

== Применение ==

Онлайн-версии алгоритмов построения дерева и леса Штейнера изучали Авербух и др. [5], а также Берман и Коулстон [7]. В области алгоритмической теории игр разработка механизмов распределения затрат в рамках групповой стратегии для задач проектирования сетей – таких как задача построения дерева Штейнера – недавно удостоилась широкого внимания исследователей; см., например, [16, 17, 19, 20]. Адаптация алгоритма AKR позволила получить подобный механизм распределения затрат для задачи построения леса Штейнера [18].

== См. также ==