Guest
Новичок
|
    
Привет!
Случилась проблема-для простой по сути задачи не хватило немного(или много) мозгов.
Задача касается теории расписаний
Есть ациклический граф, на нем изображены работы с директивным сроком.
Рассматривается максимальная вершина в ациклическом графе, директивный срок которой максимален.
Нужно доказать утверждение что: Допустимое расписание существует тогда и только тогда когда существует расписание где данная максимальная работа исполняется последней.
Может у кого то есть доказательство этого утверждения. Вроде все просто: отбрасывается максимальная вершина, смотрим что и как...и так по порядку отбрасываем вершины.
Вот и надо выяснить существует ли допустимое расписание.
Не совсем понятен метод, хотя со стороны все ясно.
Спасибо
|
Форум
Задача теории расписаний
