21
правка
Изменения
Нет описания правки
# Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
# Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
# $1 | p_i=1 | L_{max}$.
# $1 | r_i, d_i=d | L_{max}$.
# $1 | prec, r_i, p_i=1 | L_{max}$.
# Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
# $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
# $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
# $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
# $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
# $1 || \sum U_i$
# $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
# Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
# Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
