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

Экземпляр задачи построения дерева Штейнера I = (G, c, R) составляют неориентированный граф G = (V, E) с множеством вершин V и множеством ребер E, неотрицательная стоимостная функция <math>c: E \to Q^+ \;</math> и множество пар вершин <math>R = \{ (s_1, t_1 ), ...,  (s_k, t_k) \} \subseteq V \times V \;</math>. Пары в множестве R называются ''парами полюсов''. Допустимое решение задачи представляет собой подмножество <math>F \subseteq E \;</math> ребер графа G, такое, что для каждой пары полюсов <math>(s_i, t_i) \in R \;</math> существует путь между <math>s_i \;</math> и <math>t_i \;</math> в подграфе G[F], порожденном F. Пусть [[стоимость]] c(F) определяется как суммарная стоимость всех ребер в F, т.е. <math>c(F) = \sum_{e \in P} c(e) \;</math>. Задача заключается в нахождении допустимого решения F с минимальной стоимостью c(F). Легко заметить, что существует оптимальное решение, являющееся лесом.