355
правок
Изменения
→Правило Лаулера
===Реализация===
<wikitex>Пусть граф задан матрицей смежности $A = (a_{ij})$, где $a_{ij} = 1$ тогда, и только тогда, когда существует ребро $i \to j$. За $nN(i)$ обозначим число детей вершины $i$, а $schedule$ - расписписаниерасписание.
for i = 1 to n do
for j = 1 to n do
Сложность этого алгоритма $O(n^2)$.
</wikitex>
===Доказательство===
<wikitex>{{Утверждение
|statement=
Вышеописанный алгоритм строит оптимальное расписание.
|proof=
Пусть алгоритм построил расписание, в котором работы идут в порядке $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$ минимальное.
}}
</wikitex>
