Какое ограничение выполняет поток на исходной дуге ?
Сети и потоки: остаточная сеть и минимальный разрез
Сохранение потока, Форд–Фалкерсон и теорема о максимальном потоке.
Как будете решать?
Блок 1. Один верный вариант
Где требуется закон сохранения потока?
Как определяется величина потока при наличии входящих в исток дуг?
Дуга имеет ёмкость 7 и поток 3. Какова её прямая остаточная ёмкость?
Для чего нужна обратная остаточная дуга?
На сколько можно увеличить поток по дополняющему пути?
Какие дуги учитываются в ёмкости разреза ?
Когда допустимый поток максимален?
Что утверждает теорема о максимальном потоке и минимальном разрезе?
Какое условие гарантирует завершение метода Форда–Фалкерсона при произвольном выборе дополняющих путей и нулевом старте?
Блок 2. Краткий ответ
Остаточные ёмкости дуг дополняющего пути равны 5, 2 и 4. Найдите возможное увеличение потока.
целое число
По исходной дуге ёмкости 9 проходит поток 4. Какова ёмкость соответствующей обратной остаточной дуги?
целое число
Сеть содержит только дуги , , . Найдите максимальный поток.
целое число
Сеть: , , , , . Найдите максимальный поток.
целое число
Из истока выходит суммарный поток 11, в исток входит 3. Найдите величину потока.
целое число
Через разрез идут дуги из в ёмкостей 4 и 6 и дуга из в ёмкости 9. Чему равна ёмкость разреза?
целое число
Блок 3. Несколько верных вариантов
Какие условия входят в допустимость потока?
Отметьте все верные варианты
Что верно об остаточной сети?
Отметьте все верные варианты
Что гарантирует найденная пара: допустимый поток величины 12 и разрез ёмкости 12?
Отметьте все верные варианты
Какие утверждения о разрезе верны?
Отметьте все верные варианты
Завершение теста
Все ответы сохраняются автоматически. Нажмите для отправки на проверку.