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

Ребро <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>S^{ \tau} \;</math> – множество всех разрезов Штейнера, содержащихся в <math>C^{ \tau} \;</math>, т.е. <math>S^{ \tau} = C^{ \tau} \cap S \;</math>. Алгоритм AKR равномерно увеличивает двойственные значения <math>y_S \;</math> для всех множеств <math>S \in 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> становятся неактивными, в результате чего процесс завершается.