Изменения

В одну сторону утверждение очевидно<tex>\Rightarrow </tex>: тТ.к. <tex>{d'_i} \leqslant {d_i}</tex>, значит, если опозданий не было со значениями <tex>{d'_i}</tex>, их не будет и со значениями <tex>{d_i}</tex>.Докажем лемму в другую сторону<tex>\Leftarrow </tex>: пусть Пусть у нас были сроки <tex>{d_i}</tex> и мы их заменили на <tex>{d'_i}</tex> в соответствии с приведенным алгоритмом. :Пронумеруем вершины от <tex>1</tex> до <tex>n</tex> в соответствии с '''обратным''' порядком обхода в алгоритме изменения сроков. В соответствии с расписанием, время, когда деталь закончит обрабатываться на станке <tex>{C_i}</tex> удовлетворяет неравенству <tex>{C_i} \leqslant {d_i}</tex> для всех <tex>{C_1} \dots {C_n}</tex>. Тогда мы имеем <tex>{C_n} \leqslant {d_n} = {d'_n}</tex>. Если для какого-то <tex>1 < r \leqslant n</tex> мы имеем <tex>{C_n} \leqslant {d'_n}</tex> для <tex>i = r \dots n </tex> и существует работа <tex>j</tex> из этого промежутка, что вершина с номером <tex>r - 1</tex> является ее родителем, тогда <tex>C_{r-1} \leqslant \min(d_{r-1},d'_{j}-1) = d'_{r-1}</tex>

'''Первый случай.:''' <tex>t = d'_{i} - 1</tex>.

:Мы имеем <tex>x(i)>d'_{i}-1 = t</tex>. Таким образом, предок <tex>k</tex> работы <tex>i</tex> должен начать работать во время <tex>t</tex> и закончить в <tex>d'_{i}</tex>. Но т.к. <tex>d'_{k} \leqslant d'_{i} - 1 < d'_{i} = x(k) + 1</tex>, работа <tex>k</tex> так же опоздает, однако <tex>i</tex> было выбрано минимальным. Противоречие.

'''Второй случай.:''' <tex>t < d'_{i} - 1</tex>.

:В этом случае <tex>m</tex> работ <tex>j</tex> таких, что <tex>d'_{j} \leqslant d'_{i}</tex> начнут работать в момент времени <tex>t + 1</tex>, каждая из которых имеет как минимум работающего в <tex>t</tex> предка. По структуре дерева все эти предки различны, кроме того, если <tex>k</tex> {{---}} такой предок <tex>j</tex>, тогда <tex>d'_{k} \leqslant d'_{j} - 1 < d'_{j} \leqslant d'_{i}</tex>, что противоречит выбору <tex>t</tex>