Обобщенная задача построения сети Штейнера: различия между версиями

Формально исходными данными обобщенной задачи построения сети Штейнера является неориентированный мультиграф G = (V, E), в котором каждое ребро <math>e \in E \;</math> имеет неотрицательную стоимость cost c(e), а для каждой пары вершин <math>i, j \in V \;</math> имеется требование связности <math>r_{i,j} \in \mathbb{Z} \;</math>. Допустимое решение представляет собой подмножество ребер <math>E' \subseteq E \;</math>, такое, что каждая пара вершин <math>i, j \in V \;</math> соединена по меньшей мере <math>r_{i,j} \;</math> реберно-непересекащихся путей в графе G' = (V, E').