1679
правок
Изменения
Нет описания правки
=== Примеры ===
==== 1 | intree | Sum(w_i C_i) ====
Предположим, что мы уже умеем решать задачу <tex> S' = 1 \mid outtree \mid \sum w_i C_i </tex><ref>P. Brucker. Scheduling Algorithms (2006), 5th edition, p. 73 </ref>. Сведем нашу задачу <tex> S </tex> к ней следующим образом:
* Развернем все ребра, теперь если работа <tex> i </tex> зависела от работы <tex> j </tex>, работа <tex> j </tex> будет зависеть от <tex> i </tex>.
* Заменим все стоимости <tex> w_i </tex> на противоположные <tex> w'_i = - w_i</tex>.
==== 1 | prec | f_max ====
==Примечания == 1 | outtree | Sum(w_i C_i) ====<references/>
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Теория расписаний]]
