Алгоритмы: построение и анализ

<<- Назад к вопросам

Какие преобразования, приводящие задачу к эквивалентный, можно делать с матрицей цен в задаче о назначениях?

(Ответ считается верным, если отмечены все правильные варианты ответов.)

Варианты ответа

вычесть из всех чисел на главной диагонали константу

поменять местами значения в двух соседних клетках

вычесть из всех чисел в столбце константу (Верный ответ)

вычесть из всех чисел в строке константу(Верный ответ)

Похожие вопросы

Пусть в задаче о назначениях N работ. Все элементы матрици цен неотрицательны. В матрице цен есть подматрица размера m*n без нулевых элементов и m+n>N. Какие утверждения тогда верны?

При выполнении каких условий можно делать операцию PUSH(u,v)?

При выполении каких условий можно делать операцию LIFT(v) , $v \neq s, v \neq t$ ?

С помощью чего можно решать задачу поиска образца в наборе строк?

Сколько различных позиций (реальных шахматных) в задаче "эндшпиль" из лекции?

Какой тег соответствует сливанию групп городов в один в задаче коммивояжера?

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\0 & 1 & 0 & 0 & 1\\0 & 0 & 1 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

Для того чтобы решать задачу поиска подстроки в тексте, нужно построить ...