577
правок
Изменения
→Доказательство корректности
Пусть работа <tex>k_{i_0} = k</tex> была заменена работой <tex>i_0</tex>, а так же <tex>k_{i_1} \cdots k_{i_r}</tex> {{---}} последовательность работ из <tex>S</tex>, каждая из которых была на некотором шаге заменена работой <tex>i_1 \cdots i_r</tex> соответственно. Тогда <tex>i_0 < i_1 < \cdots < i_r</tex>.<br>
[[Файл:Sh.jpg|250px|thumb|right|Рис. 1. <tex>i_v</tex> превосходит <tex>i_u</tex>.]]
Будем говорить <tex>i_v</tex> ''превосходит'' <tex>i_u</tex>, где <tex>u < v</tex>, если <tex>k_{i_v} \leq i_u</tex>. Тогда <tex>w_{k_{i_v}} \geq w_{k_{i_u}}</tex>, так как когда мы вставляли работу <tex>i_u</tex> мы выбрали для замены <tex>k_{i_u}</tex>, то есть ее вес был минимальным среди всех работ, находившихся на тот момент в <tex>S</tex>, включая <tex>k_{i_v}</tex>. Для большей ясности на рисунке 1 показано, в каком порядке располагаются эти работы относительно друг другасогласно их номерам.<br>Если из последовательности <tex>i_0 < i_1 < \cdots < i_r</tex> можно выделить подпоследовательность <tex>j_0 = i_0 < j_1 < \cdots < j_s</tex> со свойствами:* <tex>j_{v + 1}</tex> превосходит <tex>j_v</tex>, где <tex>v \in [0 \cdots s - 1]</tex>* <tex>j_{s - 1} < l \leq j_s</tex>,то <tex>w_l \geq w_{k_{j_s}} \geq \cdots \geq w_{k_{j_0}} = w_k</tex>,что доказывает терему.<br>
}}
