355
правок
Изменения
→Доказательство
===Доказательство===
|statement=
Вышеописанный алгоритм строит оптимальное расписание.
|proof=
<wikitex>Пусть алгоритм построил расписание, в котором работы идут в порядке $1,2,\dots,n$. Также пусть $\sigma : \sigma(1), \dots, \sigma(n)$ {{---}} оптимальное расписание. Предположим, что $\sigma(i) = i$ для $i = n, n-1, \dots, r$ и $\sigma(r - 1) \ne r-1$, причем $r$ минимальное.Тогда имеем ситуацию, изображенную на рисунке:[[Файл:1.jpg|right]] </wikitex>
}}
