3622
правки
Изменения
м
Нет описания правки
Докажем некоторые свойства оптимального расписания, которые мы будем использовать в доказательстве корректности алгоритма.
Введем некоторые обозначения для удобства. За <tex> \mathrm{edges } </tex> обозначим список всех ребёр дерева. Для всех работ <tex>i = 1, ..., n</tex> обозначим за <tex>S(i)</tex> всех потомков <tex>i</tex> в дереве зависимостей, включая саму работу <tex>i</tex>, введём новый параметр работы <tex dpi = 150>q_i = \frac{w_i}{p_i}</tex>.
Для подмножества работ <tex>I \subseteq \{1, ..., n\}</tex> определим:
{{Теорема
|id = theorem1
|statement = Пусть <tex>i, ~j</tex> работы такие, что <tex>i</tex> {{---}} предок <tex>j</tex>, и <tex> q_j = \max \{q_k \mid ~ (i, k) \in \mathrm{edges } \}</tex>. <br>
Тогда существует оптимальное расписание, в котором работа <tex>j</tex> идёт сразу после работы <tex>i</tex>
|proof =
