Изменения
→Доказательство
|id=lemma6.12
|statement=Пусть <tex>Y = (A(t), B(t))</tex> — расписание, где <tex>B(t) = \emptyset</tex> <tex>(A(t) = \emptyset)</tex>. Тогда для каждого <tex>s > t</tex>, где <tex>B(s) = O_{ij}</tex> <tex>(A(s) = O_{ij})</tex> выполняется <tex>A(s -1) = O_{i, j - 1}</tex> <tex>(B(s - 1) = O_{i, j -1}))</tex>
|proof=Докажем по индукции по <tex>s</tex>, что если <tex>B(s) = O_{ij}</tex> и <tex>s > t</tex>, то <tex>A(s -1) = O_{i, j - 1}</tex>. Это, очевидно, верно при <tex>s = t+1</tex> так как если <tex>B(t+1) = O_{ij}</tex> и <tex>A(t)</tex> не соответствует задаче <tex>i</tex>, то <tex>B(t) = null</tex> означает что операция <tex>O_ij</tex> должна быть запланирована в разработке}расписании ранее. Предположим теперь что лемма верна для всех <tex>v</tex> при <tex>t < v < s</tex> и <tex>B(s) = O_ij</tex> . Выберем максимальное <tex>l</tex>, такое что <tex>t < l < s</tex> и <tex>B(l) = null</tex>. По предположению индукции, <tex>A(v- −1)</tex> и <tex>B(v)</tex> соответствуют одной и той же задаче для <tex>v = l + 1,...,s —- 1</tex>. Пусть <tex>A(s - 1</tex>) не соответствует задаче <tex>i</tex>. Тогда для каждого <tex> v ∈ {l, l + 1, . . . , s - 1}</tex> операция <tex>A(v)</tex> не соответствует задаче <tex>i</tex>. Таким образом, <tex>O_ij</tex> может быть обработан в момент <tex>l</tex>, что противоречит тому факту, что <tex>Y</tex> является расписанием.
}}
