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

Алгоритм основан на следующей формулировке задачи целочисленного программирования для построения леса Штейнера. Пусть I = (G, c, R) – экземпляр задачи построения леса Штейнера. Присвоим переменную-индикатор <math>x_e \in \{ 0, 1 \} \;</math> каждому ребру <math>e \in E \;</math>. Значение <math>x_e \;</math> равно 1, если e является частью леса F, и 0 в противном случае. Подмножество <math>S \subseteq V \;</math> вершин называется [[разрез Штейнера|разрезом Штейнера]], если существует по меньшей мере одна пара полюсов <math>(s_i, t_i) \in R \;</math>, такая, что <math>| \{ s_i, t_i \} \cap S | = 1 \;</math>; говорят, что S ''разделяет'' пару полюсов <math>(s_i, t_i) \;</math>. Пусть S – множество всех разрезов Штейнера. Для подмножества <math>S \subseteq V \;</math> определим <math>\delta (S) \;</math> как множество всех ребер в E, имеющих ровно одну конечную точку в S. Пусть дан разрез Штейнера <math>S \in S \;</math>; любое допустимое решение F для экземпляра I должно содержать по меньшей мере одно ребро, пересекающее разрез S, т.е. <math>\sum_{e \in \delta (S)} x_e \ge 1 \;</math>. Это приводит к следующей формулировке задачи с неориентированными разрезами: