Изменения
→Алгоритм решения
|proof=<tex>(b) \Rightarrow (a):</tex>
Рассмотрим в расширенной сети поток величиной <tex>\sum\limits_{i = 1}^n {p_i}</tex>. Обозначим через <tex>x_{iK}</tex> общий поток, который идет от <tex>J_i</tex> до <tex>I_K</tex>. Заметим, что <tex>\sum\limits_{i = 1}^n \sum\limits_{K = 2}^r x_{iK} = \sum\limits_{i = 1}^n p_i</tex>. Достаточно показать, что для каждого подмножества <tex>A \subseteq \{ 1, . . . , n \}</tex> выполняется <tex>\sum\limits_{i \in A} x_{iK} \le T_Kh(A)</tex> ,где <tex>h(A) = \begin{cases} S_{|A|}, & \text{if }|A| \le m \\ S_m, & \text{otherwise}\end{cases} </tex>.
Это означает, что условие <tex>\sum\limits_{i \in A} p_i \le Th(A), \forall A \subseteq \{ 1, ... , n \}</tex> выполняется и требования к обработке <tex>x_{1K}, . . . , x_{nK}</tex> могут быть запланированы как <tex>I_K</tex> для <tex>K = 2, . . . , r</tex>. Рассмотрим подсеть в расширенной сети индуцированной <tex>A</tex> и соответствующие части потока. Фрагмент частичного потока, который проходит через <tex>(K, j)</tex> ограничен
