Изменения
Нет описания правки
Расширенная подсеть строится путем добавления к вершинам <tex> I_K, J_{i_1}, J_{i_2}, . . . , J_{i_s} </tex> вершин <tex>(K, 1), (K, 2), . . . (K, m) </tex>.
При <tex>j = 1,..., m</tex>, есть дуги от <tex>(K, j) </tex> до <tex>I_K </tex> with capacity <tex> j(s_j - s_{j+1}) \dot T_K </tex> и для всех <tex>ν = 1,. . . , s </tex> и <tex>j = 1,. . ., m </tex> существует дуга из <tex>J_{i_ν} </tex> в <tex>(K, J) </tex> with capacity <tex> (s_j - s_{j+1}) \dot T_K </tex>.
Для каждого <tex>I_K</tex> у нас есть такие расширения. Кроме того, мы сохраняем дуги от <tex>s</tex> до <tex>J_i</tex> и мощностью <tex>p_i</tex> дуг из <tex>I_K</tex> в <tex>t</tex> мощностью <tex>S_mT_K</tex> (см. рисунок 5.2). Сеть построена таким образом, называется расширенной сетью.
{{TODO| t = Теоремы 5.9}} Следующие свойства эквивалентны:
(А) Существует допустимое расписание.
(Б) В расширенной сети существует поток от s до t со значением <tex>\sum\limits_{i=1}^{n} p_i</tex>
Из-за максимального потока в расширенной сети могут быть рассчитаны в <tex>O (m n^3)</tex> шагов, возможность проверки может быть сделано с такой же сложности.
Для решения задачи <tex>Q|pmtn; r_{i}|L_{max}</tex> мы используем бинарный поиск. Это дает <tex>\varepsilon</tex>-приближении алгоритм со сложностью <tex>O (mn^3(log(n) + log(1 / \varepsilon) + log (\max\limits_{i=1}^{n} p_i)) </tex>, потому что <tex>L_{max}</tex>, конечно, ограниченной <tex>n \max\limits_{i=1}^{n}p_i</tex>, если <tex>s_1 = 1</tex>.
//===================================================================================================================
