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

Обобщенная задача построения сети Штейнера (посмотреть исходный код)

143 байта добавлено , 6 ноября 2017

м

4431

правка

@@ Строка 37: / Строка 37: @@
 Задачу можно эквивалентно представить в виде целочисленной программы. Для каждого ребра <math>e \in E \;</math> обозначим за <math>x_e \;</math> индикаторную переменную, обозначающую, принадлежит ли ребро e к решению.
-Задача (IP)
+'''Задача (IP)'''
 Найти <math>min \sum_{e \in E} c(e) x_e \;</math>
@@ Строка 43: / Строка 43: @@
 при условиях
-S \subseteq V	(1)
+(1) <math>\sum_{e \in \delta (S)} x_e \ge f(s) \; \; \; \forall S \subseteq V</math>
-eeS(S)
-хе€{0,1}	Ve € £	(2)
+(2) <math>x_e \in \{ 0, 1 \} \; \; \; \forall e \in E</math>
-Легко увидеть, что обобщенная сеть Штейнера представляет собой специальный случай задачи (IP), где для каждого S \subseteq V выполняется f(S) = maxi2S;j26Sfri;jg.
+Легко увидеть, что обобщенная сеть Штейнера представляет собой специальный случай задачи (IP), где для каждого <math>S \subseteq V \;</math> верно <math>f(S) = max_{i \in S, j \notin S} \{ r_{i, j} \} \;</math>.