Изменения
→Доказательство
|id=theorem6.13.
|statement=Пусть <tex>O_{ij}</tex> — операция, которую планируют строчкой (*) или (**) и <tex>t = LAST(i) > T1(T2)</tex>. Тогда <tex>A(t) = \emptyset</tex> <tex>(B(t) = \emptyset)</tex>
|proof=Предположим что <tex> A(t) \neq \emptyset</tex> <tex> (B(t) \neq \emptyset)</tex>. Поскольку <tex> A(T1) = \emptyset</tex> <tex> (B(T2) = \emptyset )</tex>, из предыдущей Леммы следует, что <tex> A(t) </tex> и <tex> B(t-1) </tex> <tex> (B(t) </tex> и <tex> A(t-1)) </tex> являются операциями одной и той же задачи <tex> k</tex>. Так как <tex> LAST (i)= t</tex>, у нас должно быть значение <tex> k = i</tex>. Это невозможно, т.к. <tex> LAST (i) = t</tex> и <tex> μij \mu_{ij} = A(μij \mu_{ij} = B) </tex> подразумевают, что <tex> B(t - 1) = O_{i,j-1}</tex> <tex>(A(t - 1) = O_{i,j-1})</tex>.
}}
